In the +1/-1 prefix-sum trick for equal-counts runs, why store each total's first index?
answer
- Turn two outcomes into one number
- Balanced means the two end totals agree
- Length is end minus start position
- Which occurrence of a total maximises the span
- Write the key once, never update it
basics
~20 sBecause length is measured from the earliest position holding that running total. Recode the two outcomes as +1 and -1, and a run is balanced exactly when its two end totals match; keeping the first index and never overwriting it makes every later match yield the longest possible run.
solid answer
~40 sRecode the log so one outcome is +1 and the other -1. A stretch has equal counts of both exactly when its values sum to zero, which — using the running-total identity — means the totals at its two ends are equal. To find the LONGEST such stretch you want, for each running total, the earliest position where it occurred: when that total reappears at index `i`, the candidate length is `i - first[total]`, and any later stored occurrence would only shorten it. So the map is written only when the key is absent. Seed `first[0] = -1` for the empty prefix so a balanced run starting at element 0 measures correctly. That is the whole difference from the counting variant, which stores frequencies and updates on every visit; same identity, opposite bookkeeping.
code
pseudocode · 16 linessum = 0
first = map with { 0 -> -1 } // empty prefix sits at index -1
best = 0
for i in 0..length(log)-1:
if log[i] == MET:
sum = sum + 1
else:
sum = sum - 1
if first contains sum:
best = max(best, i - first[sum])
else:
first[sum] = i // never overwrite an earlier index
return bestgo deeper
Recall the recode: turn the two outcomes into +1 and -1 so that 'equal counts' becomes 'sums to zero'. Then say that two positions with the same running total delimit a balanced stretch.
Explain why the map keeps the earliest index for each running total and is never overwritten, and why the empty prefix is seeded at index -1. Contrast it with the counting variant, which stores frequencies and updates every visit.
Demonstrate judgment about the state you keep: bounded running totals let an indexed table replace the map, and extending past two categories changes the key from a scalar to a tuple with real memory consequences. Name what you would test.
Own the framing that several differently-worded questions are one identity with different bookkeeping. Argue for a single reviewed helper over three near-identical loops, since the seed value and write policy are exactly where copies drift into subtle bugs.
## The transform first A fitness log records, per day, whether a goal was met or missed. "Longest stretch with equally many met and missed days" looks like a counting problem, and candidates reach for two counters. Recode instead: met becomes +1, missed becomes -1. Now "equally many" is simply "the values in this stretch sum to zero", and the prefix-sum identity applies — the stretch from `l` to `r` sums to `P[r+1] - P[l]`, so it is balanced exactly when those two running totals are equal. The transform is the insight the interviewer is testing. Two-category balance, majority-by-one questions and "equal numbers of X and Y" phrasings all collapse to "find two equal running totals" once you pick +1/-1. Recognising the recode is worth more than the code that follows it. ## Why FIRST index, and never overwrite With the transform done, every pair of positions sharing a running total delimits a balanced stretch. For the longest one, when total `s` reappears at index `i`, you want the smallest index that ever held `s` — that maximises `i - first[s]`. Storing a later occurrence would only produce shorter candidates, and can never produce a longer one, because any run measured from a later start is a suffix of the run measured from the earliest start. So the map is write-once per key: `if first does not contain s: first[s] = i`. Overwriting on every visit is the classic bug, and its symptom is a plausible-looking answer that is merely too small — it reports the distance to the most recent repeat instead of the widest span. ## Why the seed is -1 here The empty prefix has running total 0 and sits at index -1, before the first element. Seed `first[0] = -1`. A balanced run covering elements 0..i then measures `i - (-1) = i + 1`, which is its true length. Seed 0 instead and every answer anchored at the start comes out one short — a distinct off-by-one from forgetting the seed altogether, and a good illustration that what you seed depends on WHAT the map stores: a count of one when counting, an index of -1 when measuring length. ## Counting versus longest, side by side | goal | map value | write policy | seed | | --- | --- | --- | --- | | how many balanced runs | occurrence count | increment every visit | total 0 -> count 1 | | longest balanced run | earliest index | write only if absent | total 0 -> index -1 | Same identity, same single pass, same O(n) expected time and O(n) worst-case space. Only the bookkeeping differs, and interviewers switch between the two mid-conversation precisely to see whether the candidate understood the identity or memorised one loop. ## Bounds worth knowing Running totals of a +1/-1 sequence over n days lie in `[-n, n]`, so the map holds at most 2n+1 keys — and if the map is keyed by an integer in a known narrow band, a plain indexed table offset by n replaces the hash map entirely, trading O(n) hashing overhead for O(n) contiguous memory with better locality. That substitution is a nice senior-level aside: the hash map is a convenience for arbitrary keys, not a requirement of the pattern. ## What breaks the transform The recode assumes exactly two outcomes. Three categories do not collapse to a single scalar total — you would need a tuple of differences as the key, which still works but multiplies the state and the memory. Say that out loud if asked to extend it; candidates who claim the +1/-1 trick generalises unchanged to k categories have not thought it through. ## The wrong answers to avoid "Track a running difference and reset it to zero when it hits zero" — that finds balanced runs starting only where a previous one ended, and misses runs that straddle. "Sort the days" — contiguity is the constraint; sorting destroys it. "Use a sliding window" — the balance is not monotone in window length, since either outcome can appear next, so no valid shrink rule exists.
- What exactly goes wrong if the map is updated on every visit instead of only when the key is absent?You measure each candidate from the most recent occurrence of that running total rather than the earliest, so every candidate is a suffix of the true one. The reported length is never too large and often close enough to look right on small inputs. Formally you lose the maximisation: `i - first[s]` is maximised by the smallest stored index, and overwriting throws that away.
- How does the bookkeeping change if the question asks how many balanced runs exist rather than the longest?Store an occurrence count per running total instead of an index, increment it on every visit rather than writing once, and seed total 0 with a count of one. At each position add the stored count for the current total to the answer before incrementing. The identity is unchanged — equal totals bracket a balanced run — only what the map remembers differs.
- The running totals here are bounded. Can you exploit that?Yes. Over n days a +1/-1 running total lies in [-n, n], so at most 2n+1 distinct keys exist and a plain indexed table offset by n can replace the hash map. You trade hashing overhead for contiguous memory and better locality, with the same asymptotics. It is a real optimisation when n is known up front and the constant factor matters.
saying these in an interview costs you the question
- Overwrites the stored index on every repeat of a total
- Seeds the empty prefix at index 0 instead of -1
- Resets a running counter to zero whenever it hits zero
- Claims the +1/-1 recode extends unchanged to three categories
- Proposes a sliding window despite the non-monotone balance