Prefix-Sum Counts

What is this?

Imagine a shop till with a paper roll that prints the running total after every item, never the price of the item itself. Someone asks whether any stretch of purchases came to exactly £12. You do not re-add anything — you scan the roll for two totals that differ by 12. The receipt has quietly recorded every possible stretch, and all you needed was a fast way to look up "have I printed this total before?"

That is this entire chapter. The array is the receipt; the hash map is the fast lookup.

💡 Fun fact: Contiguous Array asks for the longest stretch with equal 0s and 1s, which sounds nothing like arithmetic — until you map 0 → −1. Now "equal counts" means "sums to zero", and a problem about balance becomes a problem about sums. This re-encoding is the same move physicists make when they redefine a zero point: nothing about the data changed, only where you measured from.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: the sum of (i, j] is S(j) − S(i), so "is there a window ending at j with sum k?" is really "have I already seen the running total S(j) − k?" — one map lookup, and the O(n²) window scan disappears.

1. The machine

Three lines of state and one decision:

running = 0
seen = {0: 1}            # the empty prefix — see §5
answer = 0

for x in nums:
    running += x
    answer += seen.get(running - k, 0)   # every earlier match ends a valid window here
    seen[running] = seen.get(running, 0) + 1

The subtle part is the order of the two map operations. Look up before you record the current prefix. Record first and a zero-length window (k = 0) counts itself, inflating every answer by n.

And the fork that decides everything else:

For "longest", overwriting is the bug. A prefix seen at index 2 and again at index 9 must keep the 2 — the earliest start is what makes the span long. For "how many", every occurrence counts, so you always increment.

2. Where you'll actually meet this

• Cumulative metrics. Prometheus counters, billing meters and page-view totals are stored as running sums precisely because the value over any interval is a subtraction. You are implementing the query side of that design.
• Financial reconciliation. "Did any run of transactions net to zero?" is Contiguous Array with balances instead of bits — the standard way to spot a wash trade or a duplicated-then-reversed charge.
• Streaming analytics. Counting windows that satisfy a property, in one pass, without buffering the whole stream.
• Databases. Window functions (SUM(...) OVER (ORDER BY ...)) compute exactly this prefix column; the map is what an index gives you for free.
• Genomics and signal processing. GC-content balance in a DNA read, or a signal segment whose deviations cancel, is the 0 → −1 trick on a different alphabet.

3. A 30-second worked example

nums = [1, 0, 1, 0, 1], k = 2. How many subarrays sum to 2?

                    x=1   x=0   x=1   x=0   x=1
running S      0     1     1     2     2     3
S - k         -2    -1    -1     0     0     1
seen has?      -     -     -    yes   yes   yes(×2)
new windows    0     0     0    +1    +1    +2      total = 4

map after each step:
  {0:1} → {0:1,1:1} → {0:1,1:2} → {0:1,1:2,2:1} → … → {0:1,1:2,2:2,3:1}

The four windows are indices [0,2], [0,3], [1,4] and [2,4]. Note that you never enumerated one of them — the counts did. That is also why the final step contributes +2 in a single operation: prefix 1 had been seen twice, so two windows end at index 4.

4. Problems in this chapter

▶ Binary Subarrays With Sum

Count subarrays of a 0/1 array summing to goal. The machine in its plainest form — and a good place to notice that the sliding-window alternative needs the "at most k minus at most k−1" trick, while the map needs nothing clever.
Pattern: prefix sum → count. Target: O(n) time, O(n) space.

▶ Contiguous Array

The longest subarray with equal numbers of 0 and 1. Map 0 → −1 first, then it is "longest window summing to zero" — so the map stores first indices, seeded with {0: -1}.
Pattern: re-encode, then prefix sum → first index. Target: O(n) time, O(n) space.

▶ Maximum Size Subarray Sum Equals k

The general "longest window with sum k" over arbitrary integers, negatives included. This is why sliding windows do not work here — a window's sum is not monotonic when values can be negative, so shrinking on overshoot is invalid.
Pattern: prefix sum → first index. Target: O(n) time, O(n) space.

5. Common pitfalls 🚫

• Forgetting the seed. Without {0: 1}, every window that starts at index 0 is invisible — and the sample input usually still passes, because most samples have a matching window somewhere in the middle.
• Updating the map before the lookup. For k = 0 this counts each position as its own empty window.
• Overwriting a first index. For "longest", write to the map only when the key is absent. Storing the latest index quietly shortens every answer.
• Using the wrong seed for "longest". It is {0: -1}, not {0: 0} — the empty prefix sits before index 0, so a window covering the whole array computes as j − (−1).
• Reaching for a sliding window with negatives present. Two pointers require monotonicity; negative values destroy it. The map does not care.
• Overflow in other languages. Running sums over 10⁵ elements of 10⁹ exceed 32 bits — use 64-bit outside Python.

6. Key takeaways

1. sum(i, j] = S(j) − S(i) — the whole chapter is this identity plus a fast lookup.
2. Count or first index, never both. "How many" increments; "how long" records the earliest and never overwrites.
3. Seed with the empty prefix: {0: 1} for counting, {0: -1} for longest.
4. Look up before you insert, or zero-length windows contaminate the count.
5. Re-encode until it is a sum. 0 → −1 turns balance into arithmetic, and the same trick generalises to any two-symbol "equal counts" question.
6. Negatives rule out sliding windows but leave the prefix-map approach untouched — knowing why is the senior answer.

Order: Binary Subarrays With Sum → Contiguous Array → Maximum Size Subarray Sum Equals k.