Checkpoint: arrays, pointers, and windows
Debrief
What the last problem was actually testing, and what to do about whichever ones went badly.
Key idea
The idea behind the last one
If you solved the balanced-subarray problem, you found this. If you did not, here is the idea, and it is worth understanding now because the same move appears again in later units.
Treat every zero as -1 and every one as +1, then take a running total. A stretch is balanced exactly when its total is 0, which means the running total at the end equals the running total just before the start.
So the question becomes: how far apart can two equal running totals be? Store the first index at which each running total appears, and whenever you see that total again, the distance between them is a balanced stretch.
Why it works
Why that is a combination, not a new technique
The running total is Unit 1's prefix sum. Storing the first index of each value and looking it up later is Unit 1's complement map, with running totals in place of values.
Neither lesson mentioned the other. Nearly every Medium problem you meet from here on is two taught ideas standing next to each other, which is why recognizing the ideas separately is not enough.
Gotcha
Store the first index, never overwrite
The map holds the earliest index at which each running total appeared, so it must only be written when the total is new. Overwriting on every occurrence shortens every stretch you find and quietly returns a smaller answer.
The same reasoning explains the seeded entry: a running total of 0 has to be recorded as occurring before the array starts, so a stretch beginning at index 0 gets measured correctly.
Tip
What to do with a bad result
One slow problem means nothing. A pattern of slow problems in the same unit means that unit needs another pass, and the fastest fix is rereading its invariant sections rather than redoing its problems.
If the recall half was harder than the transfer half, the issue is retention rather than understanding, and the review queue handles that. If the transfer half was much harder, the issue is recognition, and the fix is to spend thirty seconds on every future problem naming which pattern it is before writing anything.
Why map zero to negative one?
In the balanced-subarray solution, zeros are counted as -1 and ones as +1. What does that transformation buy?
Match the tool to the question
Select every question below that a prefix array answers better than a sliding window.