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.