Prefix Sum Concept

Concepts covered: Prefix Sum

A dashboard lets a listener pick any range of days and shows the minutes played in it. Summing the slice for each query reads the whole range every time: 1,000 queries over a year can read up to 365,000 values, adding the same days again and again. A prefix sum does the adding once.

Build a list prefix where prefix[i] is the total of the first i days, starting with prefix[0] = 0. The total from day first through day last, both included, is prefix[last + 1] - prefix[first]: everything up to and including last, minus everything before first.

minutes = [40, 10, 25, 5, 30, 20]
prefix = [0]
for m in minutes:
    prefix.append(prefix[-1] + m)

def range_total(first, last):
    return prefix[last + 1] - prefix[first]

print(prefix)
print(range_total(2, 4))
print(range_total(0, 5))
print(range_total(3, 3))

[0, 40, 50, 75, 80, 110, 130]
60
130
5

The query for days 2 through 4 reads only the 2 entries 110 and 50, however many days lie between them. Day 3 alone works the same way: prefix[4] - prefix[3] is 80 minus 75. The build costs one pass, and each query after it costs one subtraction.

The leading 0 in the prefix list

Without the leading 0, prefix[i] would hold the total through day i, and a range starting at day 0 would subtract prefix[first - 1]. In Python that is prefix[-1], the last element, so the query returns a wrong number and raises no error. The 0 at the front gives every range, including one that starts at day 0, the same formula.

Prefix sums meet the dict

How many runs of consecutive hours have a net follower change of exactly 7? A run from hour first to hour last totals 7 when prefix[last + 1] - prefix[first] == 7, so at each hour the question is how many earlier running totals equal the current total minus 7. That's the complement lookup from two-sum, with counts in the dict instead of positions.

from collections import defaultdict

def count_runs(values, k):
    seen = defaultdict(int)
    seen[0] = 1
    running = 0
    count = 0
    for v in values:
        running += v
        count += seen[running - k]
        seen[running] += 1
    return count

print(count_runs([3, 4, 7, 2, -3, 1, 4, 2], 7))

Output:

4

The 4 runs are 3, 4, then 7, then 7, 2, -3, 1, then 1, 4, 2. The entry seen[0] = 1 stands for the empty prefix before hour 0, so a run starting at hour 0 gets counted. Negative values rule out a sliding window here, since growing a window no longer guarantees a larger total.

With prefix = [0, 40, 50, 75, 80, 110, 130] built from 6 days of minutes, which expression gives the minutes for days 1 through 3, both included?

• prefix[3] - prefix[1], the prefix entries at the 2 ends
• prefix[4] - prefix[1], which is 80 - 40 = 40
• prefix[4] - prefix[0], the total through day 3 minus the start
• prefix[3] - prefix[0], the sum of the first 3 days

Prefix code goes wrong in 2 places, and both are off by one. The list must start with 0, which gives it 1 more entry than there are days, and a query's end index must be last + 1, because entry i holds the total of the days before day i. A one-day range tests both at once: range_total(d, d) has to equal day d's own minutes. Without the + 1 it returns 0, and without the leading 0 it returns the next day's minutes instead.

About this lesson

This section is part of the Problem Solving: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.