Running Sum of 1d Array
Problem statement
You're given an array of integers nums. Build a new array runningSum of
the same length, where each position i holds the sum of every element from
the start of nums up through index i, inclusive.
Examples
Example 1
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Each value adds the next number in nums to the one before
Example 2
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Every number is 1, so the running sum just counts upward:
Example 3
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
Explanation: 3, then 3+1=4, then 4+2=6, then 6+10=16, then
Hints
runningSum[0] is always just nums[0] — there's nothing before it to
add.Approach
Optimal: Keep a running total
Intuition
Notice that each running sum only differs from the one right before it by a
single new number. So there's no need to re-add everything from the start
every time — just carry one running total forward, and add the next element
to it as you go. That's what turns O(n²) worth of repeated additions into
O(n): every number in nums gets added exactly once, ever.
Steps
- Start with
total = 0and an emptyresultlist. - For each number
xinnums, in order:- Add
xtototal. - Append the new
totaltoresult.
- Add
- Return
result.
Dry run
nums = [1, 2, 3, 4]
| step | nums[i] |
total before |
total after |
result[i] |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 |
| 1 | 2 | 1 | 3 | 3 |
| 2 | 3 | 3 | 6 | 6 |
| 3 | 4 | 6 | 10 | 10 |
Reading the last column top to bottom gives [1, 3, 6, 10] — the expected
output. Each row only adds the one new number from nums to whatever total
already was.
Edge cases: a single-element array returns that same element, since total
only gets added to once. Negative numbers work exactly the same way — total
can go up or down, and nothing about the loop needs to change for that.
Complexity
Time O(n) - each element of `nums` is added into the running total exactly once, no matter how far along the array you are.
Space O(1) - extra — one running total variable, beyond the output array.
class Solution:
def runningSum(self, nums: list[int]) -> list[int]:
result = []
total = 0
for x in nums:
total += x
result.append(total)
return result
if __name__ == "__main__":
print(Solution().runningSum([1, 2, 3, 4])) # [1, 3, 6, 10]
print(Solution().runningSum([1, 1, 1, 1, 1])) # [1, 2, 3, 4, 5]
print(Solution().runningSum([3, 1, 2, 10, 1])) # [3, 4, 6, 16, 17]RecapThe whole problem in a few lines, for the night before
- Spot it: output[i] is the sum of nums[0..i]
- Idea: one pass, each element becomes itself plus the previous running total
- Cost: O(n) time, O(1) extra space if done in place
- Trap: this is the base prefix-sum array; later problems reuse it to answer range sums fast
Interview follow-ups
What if you needed the sum of an arbitrary range
[l, r], not just from the start?Compute this same running sum once, up front, in O(n). Then any range sum is just one subtraction:
runningSum[r] - runningSum[l - 1](using0in place ofrunningSum[l - 1]whenlis0). That turns every future range query into O(1) after the one-time O(n) setup — this is exactly the idea behind Range Sum Query - Immutable.numscan change over time, and you need the running sum to stay current. What changes?Recomputing the whole running sum after every update costs O(n) each time. A Fenwick tree (binary indexed tree) supports both "update one value" and "sum of a prefix" in O(log n) each, which is worth reaching for once updates happen often.
Could you compute this without allocating a new array?
Yes — since
result[i]only ever needsresult[i - 1](which has already been computed) andnums[i], you can updatenumsin place:nums[i] += nums[i - 1]for eachifrom1onward. That drops the extra O(n) output array down to O(1) extra space, at the cost of overwriting the original input.
Frequently asked questions
Each value in the output is the sum of a prefix of the array — everything from the very start up to some index. This running-sum array is the standard building block behind range-sum queries: once you have it, you can answer "what's the sum between any two indices?" without adding anything up again.
That's exactly what the brute-force approach does under the hood — it's correct, but it re-adds almost the same numbers for every single position, which is why it costs O(n²) instead of O(n).
It's the base case for any "total so far" metric — cumulative bytes transferred over a session, cumulative deploys so far this month, a running total of retries across a batch job. Anywhere you'd plot a cumulative line on a dashboard, this is the calculation behind it.
The simple loop here is sequential, since each total depends on the one before it. At a larger scale, though, this exact operation — called an "inclusive scan" — does have well-known parallel algorithms that split the array into chunks, sum each chunk independently, and then combine the chunk totals; that's how large-scale data-processing systems compute running sums across many machines at once.