Prefix Running Sum — Problem Statement & Solution Guide
Problem Description
Given an integer n and an array nums of length n representing the points earned in each successive round, produce an array pref where pref[i] equals the sum of the first i+1 elements of nums (i.e., the running total after each round). The input consists of a line with n followed by a line with n space‑separated integers. Output the n running sums on a single line, separated by spaces.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Prefix Running Sum"
WHY DOES IT MATTER?
Prefix sums are a foundational pattern for transforming repeated aggregation queries into constant‑time lookups, a skill that recurs in array manipulation, sliding‑window, and difference‑array problems across interviews.
OPTIMIZATION CHALLENGE
The insight is recognizing that each new sum builds directly on the previous one, eliminating the need for nested loops and reducing the algorithm from quadratic to linear time while using only a single accumulator variable.
REAL-WORLD CONNECTION
Think of a bank ledger where each transaction updates the account balance; the running balance after each transaction is exactly a prefix sum, mirroring how distributed systems maintain cumulative metrics without recomputing from scratch.
During an interview, write the recurrence out loud (pref[i] = pref[i‑1] + nums[i]), then immediately translate it into a loop with a running total—this demonstrates both conceptual clarity and implementation speed.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Prefix Running Sum problem is a classic example of a cumulative aggregation over a linear data structure. The naïve mental model is to recompute the sum for each position by iterating over all previous elements, which leads to O(n^2) time—untenable for large n because each additional element forces a full re‑scan of the array. The optimal paradigm leverages the associative property of addition: the sum up to index i can be expressed as the sum up to i‑1 plus the current element, enabling a single left‑to‑right pass. This dynamic programming‑like recurrence (pref[i] = pref[i‑1] + nums[i]) transforms the problem into an O(n) time, O(1) extra‑space solution, which scales linearly with input size and fits within typical competitive‑programming and interview constraints.
Interview Questions on This Problem
Q1How would you compute the prefix sum array in a single pass without using extra auxiliary arrays?
Initialize a variable runningSum = 0; iterate through nums, add each element to runningSum, and overwrite the current index in the input array (or output directly) with runningSum. This yields the prefix array in O(1) extra space.
Q2If the input size is 10^7 and the numbers are 64‑bit integers, what considerations affect your choice of data type and I/O handling?
Use a 64‑bit type (long long in C++, long in Java, int64 in Python) to avoid overflow, and employ fast I/O (buffered readers, scanf/printf, or sys.stdin.read) because standard line‑by‑line parsing can become a bottleneck at that scale.
Q3Can you extend the prefix sum technique to answer range‑sum queries efficiently? Explain the trade‑off.
Yes—by storing the prefix array, any range sum [l, r] can be answered as pref[r] - pref[l‑1] in O(1) time. The trade‑off is O(n) preprocessing time and O(n) extra space, which is worthwhile when many queries are performed versus a single linear scan per query.
Examples
Input
5 3 -2 7 0 4
Output
3 1 8 8 12
Explanation: Round 1: 3 → sum=3; Round 2: 3+(-2)=1; Round 3: 1+7=8; Round 4: 8+0=8; Round 5: 8+4=12.
Input
3 10 10 10
Output
10 20 30
Explanation: After each round the cumulative totals are 10, then 10+10=20, then 20+10=30.
Input
6 -5 2 -3 9 -1 4
Output
-5 -3 -6 3 2 6
Explanation: Running sums: -5; -5+2=-3; -3+(-3)=-6; -6+9=3; 3+(-1)=2; 2+4=6.
Constraints
- 1 <= n <= 100000
- -10^9 <= nums[i] <= 10^9
- The absolute value of any prefix sum fits in a 64‑bit signed integer
Optimal Approach & Strategy
Maintain a running total while iterating once over nums, appending the total to the result array, achieving O(n) time and O(1) auxiliary space.
Brute Force Approach
For each index i, sum nums[0] through nums[i] by looping over the sub‑array, resulting in O(n^2) time.
Verified Code Solutions
function prefixRunningSum(nums) {
const n = nums.length;
if (n === 0) return [];
const pref = new Array(n);
pref[0] = nums[0];
for (let i = 1; i < n; i++) {
pref[i] = pref[i - 1] + nums[i];
}
return pref;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 2) {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
const result = prefixRunningSum(nums);
console.log(result.join(' '));
rl.close();
}
});#include <iostream>
#include <vector>
using namespace std;
vector<long long> prefixRunningSum(vector<int>& nums) {
int n = nums.size();
vector<long long> pref(n);
if (n == 0) return pref;
pref[0] = nums[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + nums[i];
}
return pref;
}
int main() {
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
vector<long long> result = prefixRunningSum(nums);
for (int i = 0; i < n; i++) {
if (i > 0) cout << " ";
cout << result[i];
}
cout << endl;
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static long[] prefixRunningSum(int[] nums) {
int n = nums.length;
if (n == 0) return new long[0];
long[] pref = new long[n];
pref[0] = nums[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + nums[i];
}
return pref;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] parts = br.readLine().trim().split("\\s+");
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(parts[i]);
}
long[] result = prefixRunningSum(nums);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (i > 0) sb.append(" ");
sb.append(result[i]);
}
System.out.println(sb.toString());
}
}def prefix_running_sum(nums):
"""
Compute the prefix running sum of the input array.
Args:
nums: List of integers representing points earned in each round
Returns:
List of integers where each element is the sum of all previous elements including itself
"""
n = len(nums)
if n == 0:
return []
pref = [0] * n
pref[0] = nums[0]
for i in range(1, n):
pref[i] = pref[i - 1] + nums[i]
return pref
if __name__ == "__main__":
import sys
input_data = sys.stdin.read().split()
n = int(input_data[0])
nums = list(map(int, input_data[1:n+1]))
result = prefix_running_sum(nums)
print(' '.join(map(str, result)))function prefixRunningSum(nums) {
const n = nums.length;
if (n === 0) return [];
const pref = new Array(n);
pref[0] = nums[0];
for (let i = 1; i < n; i++) {
pref[i] = pref[i - 1] + nums[i];
}
return pref;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
let lineCount = 0;
rl.on('line', (line) => {
lines.push(line);
lineCount++;
if (lineCount === 2) {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
const result = prefixRunningSum(nums);
console.log(result.join(' '));
rl.close();
}
});Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.