Running Sum of 1D Array
Running Sum of 1D Array: return an array where each position holds the sum of all elements up to and including that index.
- 1 <= nums.length <= 1000
- -10⁶ <= nums[i] <= 10⁶
Intuition
Each running total is the previous total plus one new number. So there is nothing to recompute — carry the sum forward and add a single element per step, writing the result in place.
This is the prefix-sum array in its purest form, and it is the building block behind Find Pivot Index, Subarray Sum Equals K, and Range Sum Query. Whenever a problem asks about sums of ranges, precomputing prefixes turns each range query into a single subtraction.
Approach
Before reading on: write out the running sums of [1,2,3,4] by hand and notice how much of each total you had already computed one step earlier. Aim for O(n).
The naive version recomputes what it already knew
Summing nums[0..i] afresh for every i gives the right answer in O(n²): the first position costs one addition, the last costs n. But position i differs from position i-1 by exactly one term. Re-adding the whole prefix each time throws away a result you computed one step earlier, which is the entire inefficiency.
Carry the total forward
Walk left to right keeping a single accumulator. At index i, add nums[i] to it and that is the running sum at i. Because the accumulator already holds the sum of everything before i, one addition per element is enough — n additions in total instead of n²/2. This is the prefix-sum construction in its simplest form.
Writing in place
The output has the same length as the input, and position i is read exactly once before being overwritten, so you can write into nums itself: nums[i] += nums[i-1], starting at i = 1. That drops the extra array and gives O(1) auxiliary space. If the caller must keep the original, allocate a separate result instead — the time cost is identical either way.
Solution & live demo
Common pitfalls
Starting the loop at index 0
for i in range(len(nums)):
nums[i] += nums[i - 1]for i in range(1, len(nums)):
nums[i] += nums[i - 1]At i = 0, nums[-1] is Python's last element, so the first entry is silently corrupted rather than raising an error. Index 0 already holds its own running sum and needs no work.
Recomputing the sum for every index
result = [sum(nums[:i+1]) for i in range(len(nums))]
for i in range(1, len(nums)):
nums[i] += nums[i - 1]Correct but O(n²) — each sum walks the prefix again. The point of the problem is that the previous answer already contains that work.
Reading the original value after overwriting
for i in range(1, len(nums)):
nums[i - 1] += nums[i]nums[i] += nums[i - 1]
Writing to i-1 destroys the prefix that later indices depend on, so the accumulation drifts. The write must land on the current index, whose old value is no longer needed.
Edge cases
The loop starting at index 1 never runs, and [5] is already its own running sum.
Addition handles signs naturally, so the running total may decrease — [3,1,5].
Every running sum stays 0.
With n ≤ 1000 and |nums[i]| ≤ 10⁶ the total fits comfortably in a 32-bit int.