</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Decision flow for prefix-sum counting: branch on how-many-subarrays vs longest-subarray

Worth noticing: 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.

🔓 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] 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?" 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 column S used here.

3. A 30-second worked example

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

Worked trace of counting subarrays with sum k, total 4

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 = 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 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

  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, and being able to say why is what interviewers listen for.

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

Binary Subarrays With Sum

Core idea: Sweep left to right keeping a running sum s. A subarray that ends at the current position and sums to goal is one whose starting prefix had sum s - goal. So instead of re-summing every window, keep a tally of how many times each prefix sum has occurred, and at every step add count[s - goal] to the answer. Seed the tally with {0: 1} (the empty prefix) so subarrays starting at index 0 are counted. One pass, O(1) work per element.


Problem, rephrased

A server's health log records one flag per minute: 1 if that minute logged an error, 0 if it ran clean. Ops wants to know how often error clusters of a given size occurred across the window. You're given nums, the binary array of per-minute flags, and an integer goal, the exact number of errors a time span must contain.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.