Running Sum of an Array
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 running total after reading the first i+1 numbers from the left.
Function
- 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-104 ≤ nums[i] ≤ 104- 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, then3 + 1 = 4,4 + 4 = 8,8 + 1 = 9and9 + 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, then3 + (-3) = 0.
- Input
- nums = [7]
- Output
- [7]
- Explanation
- A single number has a single running total, itself, so the answer is
[7].
+13 hidden tests on Submit
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.
How is the answer at index
irelated to the answer at indexi-1?The two sums differ by exactly one number,
nums[i]. You never need to add up a prefix from the start again.Keep one variable
total. Walk throughnumsfrom left to right, add each number tototal, and writetotalinto the answer at the same index.
Solution
Every answer is the sum of a prefix of nums, and two neighboring prefixes differ by exactly one element. Recomputing each prefix from the start repeats almost all of the work, while carrying one total forward gives every answer with a single addition. The result is the prefix sum array, the tool behind fast range sums.
Add up each prefix from scratch
Intuition
Follow the definition word for word. For every index i, start a fresh total at 0, add nums[0] through nums[i], and store the result. For [3, 1, 4, 1, 5] the last answer adds all five numbers: 3 + 1 + 4 + 1 + 5 = 14.
It is correct, but it repeats itself. The total for index 4 starts over from nums[0], even though the total for index 3, 9, already holds the sum of the first four numbers. Index i costs i+1 additions, so the whole array costs 1 + 2 + ... + n = n(n+1)/2. For n = 5000 that is about 1.25 × 10^7 additions where 5000 would do.
Apart from the answer array, which you return anyway, it keeps only a total and two indexes, so the extra space is O(1).
Algorithm
- Create an answer array of length
n. - For each index
i, settotal = 0. - Add
nums[j]tototalfor everyjfrom0toi. - Store
totalat indexiof 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 resultCarry a running total
Intuition
The sum of the first i+1 numbers is the sum of the first i numbers plus nums[i]: result[i] = result[i-1] + nums[i]. So you never look back more than one step. Keep a single variable total, add each number to it as you read it, and write the new value into the answer.
For [3, 1, 4, 1, 5], total goes 3, 4, 8, 9, 14, and those five values are the answer. Each element is read once and costs one addition, so the time is O(n). Besides the answer array, the only memory is total, so the extra space is O(1).
No total here can pass 5000 × 10^4 = 5 × 10^7 in size, which fits a 32-bit integer. With bigger inputs, prefix sums are a classic place for overflow, and a 64-bit total is the safe default.
Algorithm
- Create an answer array of length
nand settotal = 0. - Walk through the indexes from left to right and add
nums[i]tototal. - Write
totalto indexiof 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
The loop has one line of real work, so the mistakes are about where the total lives and where it goes.
- Resetting
totalinside the loop. Every answer becomesnums[i]alone, and[3, 1, 4]comes back unchanged. - Using
result[i] = result[i-1] + nums[i]without handlingi = 0. Index-1is out of bounds in most languages, and in Python it is the last element, so an in place version that starts at 0 adds the last number to the first. - Stopping the inner loop of the first approach at
j < i. It leaves outnums[i], so every answer is one number short. - Growing the answer by copying. In R,
result <- c(result, total)copies the whole vector on every step, which makes the fast approach quadratic again. Allocate the full length first. - Forgetting
*returnSize = numsSizein C. Without it the caller 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 array. It is also called the prefix sum or the 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?
With one total carried from left to right it is O(n) time, one addition per element, and O(1) extra space besides the answer. Recomputing each prefix from the start costs n(n+1)/2 additions, which 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]. Each element then holds its prefix sum, because nums[i-1] was already turned into the total of everything before it. This uses no array besides the input, but it destroys the original values.
How do prefix sums help with range sum queries?
Once you have the running sums, the total of any slice nums[l..r] is prefix[r] - prefix[l-1], or prefix[r] when l = 0. With the running sums [3, 4, 8, 9, 14], indexes 2 to 4 add up to 14 - 4 = 10. Every query takes O(1) time after one O(n) pass.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def runningSum(nums):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [3, 1, 4, 1, 5]
Expected
[3, 4, 8, 9, 14]