Prefix Sums

A small café records its takings each day: 5, 2, 6, 3, 1, 4. The owner keeps asking questions. How much from day 3 to day 5? From day 1 to day 4? Day 2 to day 6? Each answer means adding up a stretch of numbers again, and the list of days grows every week.

A car's odometer has the answer. To know how far you drove between two towns, you do not add up every metre of road. You read the odometer at each town and subtract. Keep a running total of the takings, and every "how much between here and there?" becomes one subtraction.

#The idea: running totals, then subtract

Build a second array, prefix, where prefix[i] is the sum of the first i items. It starts with prefix[0] = 0, the sum of no items at all, so it is one longer than the input.

Number the days from 0, as an array does, so days 3 to 5 are items 2 to 4. The sum of items from index l to index r, both included, is everything up to r minus everything before l:

sum(l..r) = prefix[r + 1] − prefix[l]

prefix[0] = 0for i from 0 to n - 1:  prefix[i + 1] = prefix[i] + nums[i]sum(l..r) = prefix[r + 1] - prefix[l]

function buildPrefix(nums) {
  const prefix = [0];
  for (let i = 0; i < nums.length; i++) {
    prefix.push(prefix[i] + nums[i]);
  }
  return prefix;
}
 
// Sum of nums[l..r], both ends included.
function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l];
}
 
const prefix = buildPrefix([5, 2, 6, 3, 1, 4]); // [0, 5, 7, 13, 16, 17, 21]
rangeSum(prefix, 2, 4); // 10

def build_prefix(nums):
    prefix = [0]
    for i in range(len(nums)):
        prefix.append(prefix[i] + nums[i])
    return prefix
 
# Sum of nums[l..r], both ends included.
def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]
 
prefix = build_prefix([5, 2, 6, 3, 1, 4])  # [0, 5, 7, 13, 16, 17, 21]
range_sum(prefix, 2, 4)  # 10

#Counting runs with a given total

Prefix sums get stronger next to a hash map. Take a list of daily profits and losses, [2, −1, 3, −2, 2], and ask: how many runs of days in a row add up to exactly 2?

Checking every run is O(n²). A sliding window cannot help, because the losses are negative. But the formula above says a run ending here sums to 2 exactly when an earlier running total equals current running total − 2. So walk once, keep the running total, and keep a map of how many times each running total has appeared. At each day, look up how many earlier totals would make a run of 2.

seen = {0: 1}, running = 0, count = 0for x in nums:  running += x  count += seen[running - k]  (0 if missing)  seen[running] += 1

function countRunsWithSum(nums, k) {
  const seen = new Map([[0, 1]]); // the empty start
  let running = 0;
  let count = 0;
  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}
 
countRunsWithSum([2, -1, 3, -2, 2], 2); // 5

def count_runs_with_sum(nums, k):
    seen = {0: 1}  # the empty start
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count
 
count_runs_with_sum([2, -1, 3, -2, 2], 2)  # 5

#Common mistakes

#Check yourself

#What to practise next

Solve Matching Receipts if you have not yet. It uses the same move as the run counter: for each item, look up in a map the partner it needs. Then Linked Lists trade the array's instant indexing for cheap inserts in the middle.