Know this before you start: “Running totals: prefix[i] is the sum of the first i numbers”
Running totals (prefix sums)
Walk the array once, adding as you go, and keep every total: prefix[i] is the sum of the first i numbers, with prefix[0] = 0.
The idea
A running total is what your bank balance does: each day's change is added to yesterday's balance. Write each balance down and you have a array.
Give it one extra slot at the front: prefix[0] = 0 (the sum of no numbers), and prefix[i + 1] = prefix[i] + nums[i]. For n numbers you get n + 1 totals.
Building it is one pass, . After that, every question about “the total up to here” is a lookup instead of a loop.
Worked example
Running totals of [3, −5, 2, −4]
- prefix[0] = 0: nothing added yet.
- +3 → 3, then −5 → −2, then +2 → 0, then −4 → −4.
- prefix = [0, 3, −2, 0, −4]. The lowest balance along the way was −4, the highest 3.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
nums = [3, -5, 2, -4]
nums
prefix
Solution · Pythonline 2
def prefix_sums(nums):prefix = [0] # the sum of no numbersfor x in nums:prefix.append(prefix[-1] + x) # yesterday's total + today's changereturn prefix print(prefix_sums([3, -5, 2, -4])) # [0, 3, -2, 0, -4] from itertools import accumulateprint(list(accumulate([3, -5, 2, -4], initial=0))) # the same, built inStep 1 of 6· line 2
Start with the sum of no numbers: 0. That extra slot means prefix[i] is the sum of the first i numbers.
- just added
Building it: O(n) time, O(n) space. Reading any prefix total afterwards: .
When you'll use it
- Running balances, cumulative counts, “the score after each round”.
- The first step of every range-sum and subarray-sum problem in this level.
In the wild · Analytics dashboards: “Sales between March 3 and March 17” is one subtraction of two running totals, so charts answer any date range instantly instead of re-adding every day.
Common mistakes
- Leaving out prefix[0] = 0, so sums that start at index 0 need a special case.
- Rebuilding the total with sum(nums[:i]) inside a loop: that's .