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
Running sum of 1d array returns an array where each position holds the sum of all elements up to and including it. This is the prefix-sum array in its simplest form.
Computing each entry by summing from the start is O(n²) and recomputes the same partial sums repeatedly. The improvement is immediate:
- Each running sum is the previous running sum plus the current element, so one pass suffices.
That single relation, result[i] = result[i-1] + nums[i], is the entire algorithm.
The problem permits modifying the input, so the array can be updated in place — write into nums[i] directly and return it. That gives O(1) extra space, since no second array is allocated.
Working in place requires moving left to right, so that nums[i-1] already holds its running sum when read. Iterating right to left would read raw values and produce nonsense.
The first element needs no work — its running sum is itself — so the loop starts at index 1.
A running total variable is an equally valid formulation: accumulate as you scan and write the total at each position. Identical cost, and arguably clearer about what is happening.
This pattern underpins a great many problems — Subarray Sum Equals K, Range Sum Query, Find Pivot Index — where prefix sums turn a nested loop into a lookup. Recognising it here makes those familiar.
One pass gives O(n) time and O(1) extra space.
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).
Build on the previous sum
Each running sum is the previous one plus the current element. That single relation replaces the O(n²) approach of summing from the start each time.
Work in place
The problem allows modifying the input, so write into nums[i] directly and return it — no second array, so O(1) extra space.
Iterate left to right
In-place updating requires forward order, so nums[i-1] already holds its running sum when read. Right to left would read raw values.
Start at index one
The first element's running sum is itself, so no work is needed there and the loop begins at 1.
Or track a running total
Accumulate into a variable and write it at each position. Identical cost, and clearer about the accumulation being performed.
Recognise the wider pattern
Prefix sums turn nested loops into lookups in Subarray Sum Equals K, Range Sum Query, and Find Pivot Index — this is that technique at its simplest.
Cost of the approach
One pass with constant work per element gives O(n) time and O(1) extra space.
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.