Running Sum of 1d Array

Solution Walkthrough

Approach: One Pass with a Running Total (O(n) time, O(n) output / O(1) extra)

The definition of the running sum is recursive: result[i] = result[i - 1] + nums[i], with result[0] = nums[0]. That recursion turns into a single left-to-right loop that carries one accumulator. There is nothing fancy here, and that is exactly why the pattern is so reusable: every harder prefix-sum problem reduces to this same scan plus a derived check.

Algorithm

1. Allocate an output array result of the same length as nums.
2. Initialize total = 0.
3. For each index i from 0 to n - 1:

   • Add nums[i] to total.
   • Write total to result[i].
4. Return result.

Why It Works

By induction. After step i, total equals nums[0] + nums[1] + ... + nums[i], which is the definition of result[i]. The base case i = 0 is total = 0 + nums[0] = nums[0], which matches result[0]. The inductive step i -> i + 1 adds nums[i + 1] to a value that already equals the prefix sum at i, producing the prefix sum at i + 1.

In-Place Variant (Follow-up)

If you are allowed to mutate nums, you can drop the result array and write the cumulative total back into nums[i] itself. The relation nums[i] = nums[i - 1] + nums[i] works because at the moment you read nums[i - 1] it has already been overwritten with the prefix sum, and nums[i] has not been touched yet.

export function runningSumInPlace(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

from __future__ import annotations

def running_sum_in_place(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return nums

Complexity

Metric  Value
Time    O(n), one pass over nums
Space   O(n) for the output array, or O(1) extra for the in-place variant

Pitfalls

1. Forgetting the first index. If you start the loop at i = 1 without first writing result[0] = nums[0], you will leave result[0] undefined (JavaScript) or zero (Python).
2. Reading the unwritten value in place. The in-place variant reads nums[i - 1] (already updated) and nums[i] (still original). Reversing that order corrupts the running total.
3. Negative values. The running sum is not monotonic when nums contains negatives, so do not assume the output is sorted.