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.
Worth noticing: Contiguous Array asks for the longest stretch with equal
0s and1s, which sounds nothing like arithmetic, until you map0 → −1. Now "equal counts" means "sums to zero", and a problem about balance becomes a problem about sums.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The core idea: the sum of
(i, j]isS(j) − S(i), so "is there a window ending atjwith sumk?" is really "have I already seen the running totalS(j) − k?" That is 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 section 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:
| Question | Map value | Seed | Update rule |
|---|---|---|---|
"how many subarrays sum to k" |
running count | {0: 1} |
always increment |
"the longest subarray summing to k" |
first index seen | {0: -1} |
only if absent |
For "longest", overwriting is the bug. A prefix seen at index 2 and again at index 9 must keep the 2, and 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. Monotonic counters (Prometheus counters, for example) store a running total, so the value over any interval is a subtraction of two readings. This chapter is the same subtraction applied to every interval at once.
- Ledgers. "Did any run of consecutive transactions net to zero?" is Contiguous Array with signed amounts instead of bits.
- Streaming counts. Counting windows that satisfy a sum property in one pass, without buffering the whole stream (the map still grows with the number of distinct totals).
- SQL. A running total such as
SUM(amount) OVER (ORDER BY ts)is exactly the prefix columnSused here.
3. A 30-second worked example
nums = [1, 0, 1, 0, 1], k = 2. How many subarrays sum to 2?
The four windows are indices [0,2], [0,3], [1,4] and [2,4]. 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 (it works because the values are 0 or 1), 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 = 0this 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 asj − (−1). - Reaching for a sliding window with negatives present. Two pointers require a window sum that only grows as the window grows; negative values break that. The map does not care.
- Overflow in other languages. Running sums of 10⁵ elements of size up to 10⁹ can exceed 32 bits, so use 64-bit outside Python.
6. Key takeaways
sum(i, j] = S(j) − S(i): the whole chapter is this identity plus a fast lookup.- Count or first index, never both. "How many" increments; "how long" records the earliest and never overwrites.
- Seed with the empty prefix:
{0: 1}for counting,{0: -1}for longest. - Look up before you insert, or zero-length windows contaminate the count.
- Re-encode until it is a sum.
0 → −1turns balance into arithmetic, and the same trick generalises to any two-symbol "equal counts" question. - Negatives rule out sliding windows but leave the prefix-map approach untouched, and being able to say why is what interviewers listen for.
Order: Binary Subarrays With Sum → Contiguous Array → Maximum Size Subarray Sum Equals k.
Maximum Size Subarray Sum Equals k
Core idea: A subarray's sum is the difference of two prefix sums. At each index you ask which earlier prefix had the right value, and how far back it was. To make the matching subarray as long as possible you want the earliest such prefix, so the map stores the first index each prefix sum appeared at, and you never overwrite it.
This is the "longest" cousin of Subarray Sum Equals K. That problem counts subarrays, so its map holds prefix-sum frequencies. Here we want one longest subarray, so the map holds the first index of each prefix sum. The skeleton is the same. Choosing what to store is the whole lesson.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson