Running Sum of an Array

Q: What is the running sum of an array?

It is a second array where each element is the total of everything up to and including the same position in the first. It is also called the prefix sum or cumulative sum. The running sum of [3, 1, 4, 1, 5] is [3, 4, 8, 9, 14] .

Q: What is the time complexity of computing a running sum?

O(n) time with one total carried left to right, and O(1) extra space besides the answer. Recomputing each prefix from the start is O(n²) .

Q: Can you compute the running sum in place?

Yes. Walk from index 1 to the end and set nums[i] += nums[i-1] . By then nums[i-1] already holds the total of everything up to it, so each element ends as its prefix sum. You lose the original values.

Q: How do prefix sums help with range sum queries?

The total of a slice nums[l..r] is prefix[r] - prefix[l-1] , or prefix[r] when l = 0 . With [3, 4, 8, 9, 14] , indexes 2 to 4 add up to 14 - 4 = 10 . Each query takes O(1) after one O(n) pass.

BeginnerPrefix sum

+10

You get an array of integers nums. Return a new array of the same length whose element at index i is nums[0] + nums[1] + ... + nums[i], the total of the first i+1 numbers.

Function

runningSum(nums: integer-array) → integer-array

numsinteger-array: the numbers to add up from left to right
Returnsinteger-array: the running totals, one for each element of nums

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Every running total fits in a 32-bit signed integer.

Examples

Input: nums = [3, 1, 4, 1, 5]
Output: [3, 4, 8, 9, 14]
Explanation: Keep adding: 3, then 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 and 9 + 5 = 14. Each total goes to the index of the number added last.

Input: nums = [-2, 5, -3]
Output: [-2, 3, 0]
Explanation: Negative numbers pull the total down: -2, then -2 + 5 = 3, then 3 + (-3) = 0.

Input: nums = [7]
Output: [7]
Explanation: A single number has one running total, itself, so the answer is [7].

Follow-up

Can you build the same thing for a grid, where each cell holds the total of the rectangle from the top-left corner to that cell?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every answer is the sum of a prefix of nums, and neighboring prefixes differ by one element. Recomputing each prefix from the start repeats almost all the work. Carry one total forward instead and each answer costs a single addition.

Add up each prefix from scratch

Intuition

Follow the definition: for every index i, start a total at 0, add nums[0] through nums[i], and store it. It is correct because each answer is computed exactly as defined.

Index i costs i+1 additions, so the array costs n(n+1)/2: about 1.25 × 10^7 additions for n = 5000, where 5000 would do.

Algorithm

Create an answer array of length n.
For each index i, set total = 0.
Add nums[j] to total for every j from 0 to i.
Store total at index i of the answer, and return the answer after the last index.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Carry a running total

Intuition

The sum of the first i+1 numbers is the sum of the first i plus nums[i]: result[i] = result[i-1] + nums[i]. So you never look back more than one step, and one variable total is enough. For [3, 1, 4, 1, 5] it goes 3, 4, 8, 9, 14, which is the answer.

Each element costs one addition: O(n) time, and O(1) extra space besides the answer.

Algorithm

Create an answer array of length n and set total = 0.
Walk through the indexes from left to right and add nums[i] to total.
Write total to index i of the answer.
Return the answer.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Pitfalls and edge cases

Resetting total inside the loop. Every answer becomes nums[i] alone, and [3, 1, 4] comes back unchanged.
Reading result[i-1] at i = 0. Most languages go out of bounds; Python reads the last element, so an in place version adds the last number to the first.
Stopping the brute force's inner loop at j < i. It leaves out nums[i], so every answer is one number short.
In R, growing the answer with result <- c(result, total) copies the vector on every step and makes the fast approach quadratic. Allocate the full length first.
In C, forgetting *returnSize = numsSize. The caller then does not know how many totals to read.

Frequently asked questions4

What is the running sum of an array?

It is a second array where each element is the total of everything up to and including the same position in the first. It is also called the prefix sum or cumulative sum. The running sum of [3, 1, 4, 1, 5] is [3, 4, 8, 9, 14].

What is the time complexity of computing a running sum?

O(n) time with one total carried left to right, and O(1) extra space besides the answer. Recomputing each prefix from the start is O(n²).

Can you compute the running sum in place?

Yes. Walk from index 1 to the end and set nums[i] += nums[i-1]. By then nums[i-1] already holds the total of everything up to it, so each element ends as its prefix sum. You lose the original values.

How do prefix sums help with range sum queries?

The total of a slice nums[l..r] is prefix[r] - prefix[l-1], or prefix[r] when l = 0. With [3, 4, 8, 9, 14], indexes 2 to 4 add up to 14 - 4 = 10. Each query takes O(1) after one O(n) pass.

def runningSum(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [3, 1, 4, 1, 5]

Expected Output

[3, 4, 8, 9, 14]