Running Sum of 1d Array — Solution

Problem

Given a list of numbers, produce a new list where every element is replaced by the sum of all elements up to and including that position. Each output element "accumulates" everything before it.

For example, given [1, 2, 3, 4]:

• Input: nums = [1, 2, 3, 4]
• Output: [1, 3, 6, 10]
• Explanation: Position 0 stays 1; position 1 becomes 1+2=3; position 2 becomes 1+2+3=6; position 3 becomes 1+2+3+4=10.

Counter-example: [3, 3, 3, 3] → [3, 6, 9, 12] — the output is NOT [3, 3, 3, 3], because each element accumulates, not restarts.

Intuition

Every element in the running sum only needs the previous running sum total — not a fresh re-sum from index zero. A single left-to-right pass is enough: each position absorbs the accumulated total from its left neighbor. No two-pass approach or extra data structure is needed.

Solution — In-Place Prefix Sum

Scan from left to right, adding each element to its left neighbor. The first element stays unchanged since there's nothing before it.

1. Start the loop at index 1 (index 0 is already its own prefix sum).
2. For each index i, add nums[i-1] (the running total so far) into nums[i].
3. Return the modified array.

1def runningSum(nums: list[int]) -> list[int]:
2    for i in range(1, len(nums)):
3        nums[i] += nums[i - 1]  # carry the accumulated total forward
4    return nums

Time: O(n) — a single pass over all n elements.
Space: O(1) — the input array is modified in place; no auxiliary storage is needed.

Complexity Summary

Common Mistakes

• Starting the loop at index 0 instead of 1 — processing nums[0] adds nums[-1] in Python (the last element) or reads out of bounds in other languages, corrupting the result before the scan even begins.
• Re-summing from scratch at each index — writing nums[i] = sum(nums[:i+1]) for every i gives the right answer but runs in O(n²) time, which is entirely unnecessary here.
• Forgetting that nums[0] is already correct — the first element is the running sum of just itself, so it never needs to change.
• Allocating a new result array when in-place modification works — the problem allows modifying the input directly, so a second O(n) array wastes memory with no benefit.

Related Problems

• subarray-sum-equals-k — pairs prefix sums with a hash map to count subarrays summing to a target in O(n)
• product-of-array-except-self — the same left-to-right accumulation idea, applied to products instead of sums
• contiguous-array — prefix sum variant that finds the longest subarray with equal 0s and 1s
• minimum-path-sum — prefix accumulation extended across a 2D grid
• maximum-subarray — Kadane's algorithm shares the same "carry forward only what's useful" insight as prefix sum thinking