Running Sum of 1d Array
Build a prefix-sum array in one pass — the foundation of every range-sum technique
Problem Statement
Given an array nums, return an array result where result[i] is the sum of nums[0] … nums[i].
Input: nums = [1, 2, 3, 4]
Output: [1, 3, 6, 10]
Why: [1, 1+2, 1+2+3, 1+2+3+4]
Input: nums = [1, 1, 1, 1, 1]
Output: [1, 2, 3, 4, 5]
Input: nums = [3, 1, 2, 10, 1]
Output: [3, 4, 6, 16, 17]Intuition
The literal reading of the problem suggests: for each position i, add up everything from 0 to i. That is a loop inside a loop — O(n²) — and it repeats work endlessly. Computing result[3] re-adds the exact numbers you already added for result[2].
The key insight
Each answer is one addition away from the previous answer:
result[i] = result[i-1] + nums[i]
The running total is the memory. You never look backwards, you just keep accumulating.
This tiny problem is worth taking seriously because the array it produces — the prefix sum array — is the setup step for a whole family of harder problems. Once you have it, the sum of any range [i, j] becomes a single subtraction:
sum(i..j) = prefix[j] - prefix[i-1]That turns "sum this range" from an O(n) loop into O(1) arithmetic.
Real-world analogy
It's a bank statement. The balance column is never recomputed from the beginning of time — each row is just previous balance + today's transaction.
Approach
Keep one accumulator
A single variable total, starting at 0.
Walk the array once
At each element, add it to total, then append (or write) total into the output.
Or modify in place
Because result[i] depends only on result[i-1] and nums[i] — both already final — you can overwrite nums itself and use no extra space.
Watch it run
Solution
def running_sum(nums: list[int]) -> list[int]:
"""Return the prefix sums of nums."""
result: list[int] = []
total = 0
for num in nums:
total += num
result.append(total)
return resultIn place, using no extra array:
def running_sum_in_place(nums: list[int]) -> list[int]:
for i in range(1, len(nums)):
nums[i] += nums[i - 1]
return numsPython also ships this in the standard library:
from itertools import accumulate
def running_sum_stdlib(nums: list[int]) -> list[int]:
return list(accumulate(nums))Why Prefix Sums Matter
Suppose you must answer many questions of the form "what is the sum of nums[2..5]?" on the same array.
nums = [3, 1, 2, 10, 1]
prefix = [3, 4, 6, 16, 17]
sum(1..3) = prefix[3] - prefix[0] = 16 - 3 = 13
check: 1 + 2 + 10 = 13 ✓Building the prefix array costs O(n) once; after that every range query is O(1) instead of O(n). With 1,000 queries on a 1,000-element array that is 1,000 operations instead of 1,000,000.
Watch the off-by-one
sum(i..j) = prefix[j] - prefix[i-1], and when i = 0 there is no prefix[-1]. Two common fixes: special-case i == 0, or build the prefix array with a leading 0 so that sum(i..j) = prefix[j+1] - prefix[i] always works.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — one pass, one addition per element.
- Space —
O(n)for the output array, orO(1)extra if you rewrite the input in place.
Edge Cases
Related Problems
- Find Pivot Index — prefix sums used to split an array into balanced halves
- Maximum Average Subarray I — a sliding window, which is a prefix sum you carry rather than store
- Product of Array Except Self — the same prefix idea, with multiplication and a second pass from the right