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]

  1. prefix[0] = 0: nothing added yet.
  2. +3 → 3, then −5 → −2, then +2 → 0, then −4 → −4.
  3. 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.

prefix ← [0](the sum of no numbers)
for each x in nums:
append last total + x
prefix[i] = sum of the first i numbers

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

03
1-5
22
3-4

prefix

00

Solution · Pythonline 2

def prefix_sums(nums):
prefix = [0] # the sum of no numbers
for x in nums:
prefix.append(prefix[-1] + x) # yesterday's total + today's change
return prefix
print(prefix_sums([3, -5, 2, -4])) # [0, 3, -2, 0, -4]
from itertools import accumulate
print(list(accumulate([3, -5, 2, -4], initial=0))) # the same, built in

Step 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 .

Practise it · before the Prefix Sum problems

Lowest balance

An account starts at 0 and nums are the changes, in order. Return the lowest balance it ever has, counting the starting 0.

Input nums = [3, -5, 2, -4]

Output -4

Balances: 0, 3, −2, 0, −4.

Input nums = [2, 3]

Output 0

It never drops below the starting 0.

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?