In a sliding window tracking distinct keys, why can the distinct count read too high?
answer
- the map remembers more than the window does
- what happens when a count hits zero
- map key count versus keys actually inside
- derived scalars move only at crossings
- duplicates are what expose it
basics
~20 sDecrementing a key's count to zero without erasing the entry leaves a dead key, so a distinct count read from the map's key count includes keys the window no longer holds. Erase at zero, or count only crossings.
solid answer
~50 sThe bookkeeping has an invariant: the map's key set must equal exactly the keys currently inside the window. A removal that does `count[k] = count[k] - 1` and stops breaks it — the key survives at value zero, and any code reading the number of distinct elements as the map's key count now over-reports. There are two clean fixes. Erase the key when its count reaches zero, so the key set stays honest; or keep an explicit `distinct` integer and move it **only at crossings** — increment when a key goes from 0 to 1, decrement when it goes from 1 to 0. The mirror-image bug is decrementing that integer on every removal, which under-reports as soon as a key appears more than once. Both bugs pass any test whose input has no repeated keys, which is why they survive review.
code
pseudocode · 13 lines// window over shift records; count maps a tag to its multiplicity inside
// element entering on the right
r = tag[right]
count[r] = count[r] + 1
...
// element leaving on the left
l = tag[left]
count[l] = count[l] - 1
...
// validity test, evaluated after every move
// size(count) == number of keys present in the map
if size(count) <= K
record_best(left, right)go deeper
Remember that a count reaching zero does not remove the key. If you read the number of distinct elements from the map's key count, erase each entry as it hits zero.
State the invariant precisely — the map's key set equals the keys actually inside the window — and show exactly where the removal step must test for the zero crossing.
Show how you would catch it: assert the invariant after every removal, and differential-test against a brute-force recomputation on duplicate-dense input that shrinks and regrows the window.
Take a position on derived state in general. Every counter mirroring a collection is a second source of truth, and you decide when the team maintains one and when the code recomputes instead.
## The invariant being violated Window bookkeeping over a multiset rests on one statement: **the map's key set is exactly the set of keys currently inside the window, and each value is that key's multiplicity inside the window.** Everything derived from the map — the distinct-key count, an "is any key repeated" flag, a satisfied-requirements counter — is only correct while that statement holds. A removal step that decrements a count and stops satisfies half of it. The multiplicities stay right: a key inside the window three times genuinely reads 3. But the key set drifts, because a key whose multiplicity fell to zero is still a key in the map. If distinct-ness is read as "how many keys does the map have", the answer is now the number of keys that have *ever* been in the window since the map was created, not the number in it now. On a sweep that shrinks and regrows repeatedly, that number only climbs. ## Why the bug survives testing The drift needs a key to leave the window and the code to keep going. On input where every key is unique and the window only grows, no count ever returns to zero on a key that matters, and the derived number is right by accident. Hand-written examples tend to look exactly like that. The failing shape is duplicate-dense input where the window shrinks and then grows again — a rotation where the same certification appears repeatedly, and the span narrows and widens as it walks. The symptom is also indirect. Nothing crashes and no count goes negative. A window is simply judged to contain more distinct keys than it does, so a search for the narrowest span covering at most `k` distinct keys rejects spans that were fine, and returns an answer that is merely *a* valid answer rather than the best one — or no answer at all. Off-by-one in a reported width is a much quieter failure than an exception. ## The two correct disciplines **Erase at zero.** After the decrement, if the value is zero, remove the key. The key set now matches the window at all times, and reading the number of keys is a correct distinct-count. This is the smaller-diff fix and the one with the fewest moving parts. **Maintain a counter at crossings.** Keep an integer `distinct` beside the map. On entry, after incrementing, if the value just became 1, increment `distinct`. On removal, before or after decrementing, if the value just became 0, decrement `distinct`. The rule generalises: **a scalar derived from a multiset changes only when some key crosses a threshold, never on every update.** Occurrences two through five of a key change nothing about how many distinct keys exist. The two disciplines can be combined, and one reason to prefer the maintained counter with entries retained is churn: repeatedly erasing and re-inserting the same key does allocation and, depending on the table's deletion strategy, can leave tombstones or force reorganisation. Retaining zero-valued entries avoids that churn, and is a perfectly good design — as long as nothing ever reads distinct-ness from the key count again. Choosing one representation and never reading the other is the actual rule. ## The twin bug The mirror image shows up in a maintained counter that is decremented on *every* removal instead of only on the crossing. Now the counter falls below the true distinct count as soon as any key appears more than once, and the window is judged to hold fewer distinct keys than it does. Where the stale-entry bug is too permissive in one direction, this one is too permissive in the other; both come from the same missing idea, that derived scalars move at thresholds. The same mistake reappears one level up in any counter that tracks how many requirements a window satisfies: it must move when a key reaches or drops below its required multiplicity, not on every occurrence added or removed. ## Catching it deliberately Two cheap habits find this class of bug before an interview panel does. **Assert the invariant.** In a debug build, after every removal, assert that no entry in the map has value zero (under the erase-at-zero discipline), or that the maintained counter equals the number of entries with a positive value (under the counter discipline). The assertion is `O(keys)` and is meant to be switched off in production, but it fails on the very first shrink that goes wrong. **Differential-test against recomputation.** Run the incremental version beside a brute-force recomputation of the window state at every position, over generated input drawn from a deliberately tiny key alphabet so duplicates are dense, and over a movement pattern that shrinks and regrows many times. Any divergence names the exact step where the invariant broke, which is far more useful than an off-by-one in the final answer.
- What is the mirror-image bug, where the distinct count reads too low instead?Decrementing the maintained counter on every removal rather than only when a key's multiplicity crosses to zero. Remove one of three copies of a tag and the counter drops even though the tag is still inside, so the window is judged to hold fewer distinct keys than it does. Both bugs come from ignoring that derived scalars move only at thresholds.
- The code passes every test you wrote. How would you build a test that actually fails?Generate input over a deliberately tiny key alphabet so duplicates are dense, and drive a movement pattern that shrinks and regrows the window many times. Compare the incremental state against a brute-force recomputation at every position; the first divergence names the exact step. Separately, assert after each removal that no entry sits at zero.
- Is it ever right to leave zero-valued entries in the map on purpose?Yes. Erasing and re-inserting the same key repeatedly costs allocation and, depending on the table's deletion strategy, leaves tombstones or forces reorganisation. Retaining the entries avoids that churn. The condition is absolute, though: distinct-ness must then come from a maintained counter, and nothing may ever read it from the map's key count again.
A guest list that nobody ever checks people out of still looks full after the party ends. Erasing a key at zero is the checkout step.
saying these in an interview costs you the question
- The map's key count is the distinct count, always
- Zero-valued entries are harmless, they only waste space
- Decrement the distinct counter on every removal
- It passed my tests, so the bookkeeping is correct
- Just recount the map each step, it is small anyway