Prefix Sums Example: Counting Ledger Stretches That Total Exactly Two

A run sums to k exactly when two prefix totals differ by k, so a map of the totals seen so far counts the runs in one pass.

Prefix sums with a hash map of counts count the runs that add up to a target k in one pass. A run from i to j sums to k exactly when p[j + 1] − p[i] = k, that is when an earlier total equals the current total minus k. A map from each total seen so far to how often it appeared answers that in one lookup.

A small ledger records the changes to an account in pounds, 2 −1 1 2, and the question is how many stretches of consecutive entries total exactly 2.

How many stretches total exactly 2?

4: the first 2 on its own, 2 −1 1, −1 1 2, and the last 2 on its own. The steps find all four without listing them.

The map starts as {0: 1}, the total of no entries, so that a stretch starting at the first entry is counted. At each entry, add it to the running total, look up total − 2 and add its count to the runs, then record the total. Looking up before recording keeps an empty stretch from counting itself.

One pass over the ledger 2 −1 1 2 for the total 2

Entry 2

text

running total 2
look up 2 - 2 = 0: seen 1 time, runs 1
map after: {0: 1, 2: 1}

Entry −1

text

running total 1
look up 1 - 2 = -1: not seen, runs 1
map after: {0: 1, 2: 1, 1: 1}

Entry 1

text

running total 2
look up 2 - 2 = 0: seen 1 time, runs 2
map after: {0: 1, 2: 2, 1: 1}

Entry 2

text

running total 4
look up 4 - 2 = 2: seen 2 times, runs 4
map after: {0: 1, 2: 2, 1: 1, 4: 1}

The listing prints the same steps from a run.

ledger.pypy

def count_runs_with_total(entries: list[int], k: int) -> int:
    seen: dict[int, int] = {0: 1}
    total = runs = 0
    for entry in entries:
        total += entry
        found = seen.get(total - k, 0)
        runs += found
        seen[total] = seen.get(total, 0) + 1
        print(f"entry {entry}: total {total}, look up {total - k}, found {found}, runs {runs}, map {seen}")
    return runs


print("runs totalling 2:", count_runs_with_total([2, -1, 1, 2], 2))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

entry 2: total 2, look up 0, found 1, runs 1, map {0: 1, 2: 1}
entry -1: total 1, look up -1, found 0, runs 1, map {0: 1, 2: 1, 1: 1}
entry 1: total 2, look up 0, found 1, runs 2, map {0: 1, 2: 2, 1: 1}
entry 2: total 4, look up 2, found 2, runs 4, map {0: 1, 2: 2, 1: 1, 4: 1}
runs totalling 2: 4

The last entry found two stretches at once, because the total 2 had been seen twice: once after the first entry and once after the third. The pass is O(n) time and O(n) extra space for n entries. A sliding window cannot count these stretches, because the −1 means dropping an entry can raise the total, which is the case the Sliding Window topic's gotcha warns about.

← → move through sections and cards