In a sliding window, why keep a need-vs-have match counter instead of comparing full maps each step?
answer
- how often is validity actually tested
- cost of re-reading every requirement per move
- one integer standing in for the whole check
- count satisfied keys, not occurrences
- the counter moves only at the threshold
basics
~20 sComparing the window's counts against every requirement costs work proportional to the requirement count on every move, so the sweep becomes O(n*R). One integer counting how many requirements are satisfied turns the validity test into a single comparison.
solid answer
~50 sValidity here is "for every required key `k`, the window holds at least `need[k]` of it". Checking that literally walks all `R` distinct requirements on every grow and every shrink, so a linear sweep costs `O(n*R)`. Instead keep `matched` = the number of required keys currently satisfied. When a key enters, bump its count and increment `matched` **only if the count just reached `need[k]`**. When one leaves, decrement `matched` **only if the count was exactly `need[k]` before dropping**. Validity is then `matched == R`, in one comparison. The crossing conditions are the entire trick — moving `matched` on every occurrence is the classic bug, and extra copies beyond the requirement must change nothing. In review I would not always call the naive compare a defect: when `R` is a small fixed constant and the loop is not hot, `O(R)` with a tiny constant is fine and carries one fewer invariant. I flag it when `R` scales with the input or the sweep sits on a hot path.
go deeper
Know what the counter is for: it answers "is this window valid yet" with one comparison instead of walking every requirement. Be able to state the validity condition in plain words.
Explain the crossing rule exactly — the counter moves only when a key reaches or drops below its required amount — and give the cost of the naive per-move compare across the whole sweep.
Show the review judgment: name the workload where the per-move compare is a real regression, and the one where it is fine because the requirement set is bounded independently of the input.
Own the tradeoff between the faster sweep and one more invariant. Decide when a team standardises on the counter, when the readable version wins, and how the fast one is kept honest under later edits.
## The setup Take an on-call rotation checker. Shift records stream past in order, each carrying a skill tag, and a valid stretch of the rotation is one that covers every required capability — two people certified for the database tier, one for the network tier, one incident commander. The requirement is a **multiset**: `need[k]` says how many records carrying key `k` a window must contain, and the window's own map, call it `have`, says how many it actually contains. Validity is the predicate: > for every key `k` in `need`: `have[k] >= need[k]` Note what it is *not*. It is not `have == need` — a window holding three database-certified people when two are required is perfectly valid. Extra copies beyond the requirement are harmless, and any bookkeeping that treats them as significant is wrong. ## Why evaluating the predicate literally is expensive The predicate is checked constantly. A window sweep touches roughly `2n` positions — every element enters once and leaves once — and validity is consulted after each move to decide whether the window may shrink or must grow. Evaluating it literally walks all `R` distinct required keys and does a lookup per key, so the whole sweep costs `O(n*R)` rather than `O(n)`. The seductive wrong answer is that the compare is `O(1)` "because the requirement set is a constant". Sometimes it genuinely is a small fixed constant, and then the claim is defensible in practice if not in notation. But requirements frequently come from the input — the required capability set is itself derived from the roster being checked — and then `R` grows with the problem and the sweep is quadratic in disguise. Reviewing a diff, the question to ask is not "is `R` small today" but "is `R` bounded by something independent of the input". ## The counter and its exact update rules Maintain one integer, `matched`, defined as: > `matched` = the number of keys `k` in `need` for which `have[k] >= need[k]` Since `matched` counts *keys*, never occurrences, it is bounded by `R`, and validity is exactly `matched == R` — a single comparison, `O(1)`. Repairing it as the window moves: - **On entry of key `x`:** increment `have[x]`. Then, if `x` is required and `have[x]` is now *exactly* `need[x]`, increment `matched`. If `have[x]` overshoots `need[x]`, nothing changes — the key was already satisfied and is still satisfied. - **On removal of key `x`:** if `x` is required and `have[x]` is *exactly* `need[x]` right now, decrement `matched` — the removal is about to break this requirement. Then decrement `have[x]`. The equality tests are the whole mechanism. `matched` moves only when a key **crosses** its requirement boundary, in either direction; it is untouched by every occurrence above the boundary and every occurrence below it. Because each key crosses at most once per entry and once per removal, total maintenance across the sweep is `O(1)` per move, and the counter is exactly as correct as the crossing tests are. ## The two bugs this design attracts **Incrementing on every occurrence.** `matched` then counts records rather than satisfied requirements, overshoots `R`, and a window is declared valid the moment it holds enough records of *any* mix — the requirement set stops being enforced at all. Comparing with `>=` instead of `==` merely hides it. **Decrementing on every removal.** The counter falls below the true number of satisfied requirements as soon as a key is present in excess, so a still-valid window is judged invalid and the algorithm keeps growing past the real answer. This is the same threshold mistake as the one that makes a distinct-key count drift, one level up. Both pass tests where the requirement multiset has no duplicates and the input has no excess copies — the shape most people write by hand. ## The review judgment Seen in a diff, a per-step full compare is not automatically a defect. Weigh three things. **Is `R` bounded independently of the input?** A hard-coded set of six capability tags means the compare is a small constant factor and the sweep stays linear in practice. A requirement set parsed from the input means `O(n*R)`, and at ten times the current input size that is the thing that falls over. **Is the sweep hot?** A validation run nightly over one roster does not care. The same code inside a request path, or run across every rotation in a fleet, does. **What does the counter cost in maintenance?** It is a second source of truth with two asymmetric crossing conditions, and it is the exact thing a future edit breaks silently. The honest review comment names the workload, not the notation: "if the capability set can come from the roster, this is quadratic — here is the counter; if it stays hard-coded at six, leave it and add a comment saying why." ## Summary of costs | Approach | Validity test | Sweep | Extra state | |---|---|---|---| | Compare all requirements each move | O(R) | O(n*R) | none | | Maintained match counter | O(1) | O(n) | one integer, two crossing rules |
- State the exact condition for incrementing the match counter when a key enters the window.Increment the key's count first, then increment `matched` only if the count is now exactly equal to that key's required amount. Overshooting changes nothing, because the requirement was already satisfied. On removal it is the mirror: decrement `matched` only when the count is exactly the required amount immediately before dropping below it.
- The requirement multiset has duplicates — two people must hold the same certification. Does the counter still work?Yes, unchanged in structure. The required amount is a count, not a flag, so the crossing test compares against that count rather than against 1. `matched` still counts distinct required keys whose held amount meets or exceeds the requirement, and validity is still the single comparison against the number of distinct requirements.
- When would you leave a per-step full requirement compare alone in review?When the number of distinct requirements is bounded independently of the input — a hard-coded capability set — and the sweep is not on a hot path. The compare is then a small constant factor and it removes an invariant with two asymmetric crossing rules. I would ask for a comment stating that bound, so a later change that derives requirements from input gets caught.
A checklist with a running count of unticked lines at the top: you glance at the number instead of re-reading every line each time something changes.
saying these in an interview costs you the question
- Comparing the two maps every step is O(1)
- Increment the match counter on every occurrence added
- The counter equals the number of keys in the window
- Extra copies beyond the requirement make the window invalid
- Validity means the window's counts equal the requirement exactly