Running Sum of 1d Array

Running Sum of 1d Array

What is this problem about?

The Running Sum of 1d Array interview question asks you to transform an array by replacing each element with the sum of all elements from the beginning of the array up to and including that position. This is the prefix sum operation — one of the most foundational building blocks in array-based algorithms.

Why is this asked in interviews?

This problem is asked at Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe as the most basic introduction to the prefix sum technique. Understanding prefix sums is a prerequisite for range sum queries, subarray sum problems, sliding window optimization, and difference arrays. Solving this cleanly signals readiness for all those higher-complexity problems.

Algorithmic pattern used

The pattern is prefix sum computation. Iterate through the array from index 1 to the end, updating each element: nums[i] += nums[i-1]. This builds the prefix sum in-place. Alternatively, create a new array where result[i] = result[i-1] + nums[i]. Both are O(n) time. In-place is O(1) space; the new array approach is O(n) space.

Example explanation

Input: [3, 1, 2, 10, 1]

In-place:

• i=1: 1 + 3 = 4. Array: [3, 4, 2, 10, 1].
• i=2: 2 + 4 = 6. Array: [3, 4, 6, 10, 1].
• i=3: 10 + 6 = 16. Array: [3, 4, 6, 16, 1].
• i=4: 1 + 16 = 17. Array: [3, 4, 6, 16, 17].

Result: [3, 4, 6, 16, 17].

Verification: result[2] = 3 + 1 + 2 = 6. ✓

Common mistakes candidates make

• Modifying the array while reading from it incorrectly — in-place update with nums[i] += nums[i-1] works because nums[i-1] is already the prefix sum up to i-1.
• Starting the loop at index 0 instead of 1, which would add nums[-1] incorrectly.
• Creating a result array of the wrong size — must be the same length as the input.
• Not understanding the difference between prefix sum and suffix sum (this problem is prefix).

Interview preparation tip

For the Running Sum of 1d Array coding problem, the array and prefix sum interview pattern is the foundation of many harder problems. Solve this in one pass, in-place. Interviewers at Meta and Adobe often follow up immediately with range sum queries or subarray sum equals K — know that prefix sums make range queries O(1): range_sum(l, r) = prefix[r] - prefix[l-1]. Master this building block before moving to harder problems.