When does a sliding window need a frequency map instead of just a running sum?
answer
- what does the answer actually depend on
- can the leaving element be subtracted exactly
- totals collapse, identities do not
- distinct keys force one count per key
- a map costs memory and hashing per move
basics
~20 sA running sum suffices when the answer is a single reversible total, like hours worked. A per-key frequency map is needed when the answer depends on which distinct keys are present, not just on a total.
solid answer
~40 sAsk two things before choosing the state. First: can the leaving element's contribution be subtracted exactly? Totals and per-element counts can, so one integer carries the whole window. Second: does the answer depend on identities? "Total hours in this window" and "how many shifts ran over eight hours" do not, so they stay scalar. "How many distinct skill tags does the window cover" and "does the window contain every required tag" do, so they need a count per key, plus a small derived scalar maintained alongside it. The lazy default of "just always keep the map" is not free: the map costs memory proportional to the distinct keys inside the window and a hashing step on every move, and each extra piece of derived state is one more invariant that can silently go wrong.
go deeper
Be ready to say what the window state has to answer before you pick it. Practise the one-liner: a total needs one number, distinct keys need one count per key.
Explain the reversibility test out loud — can the leaving element's contribution be subtracted exactly — and give the per-move time and the space each option costs.
Expect to defend the smaller state on a hot path: memory per distinct key, hashing on every move, and one fewer invariant to break. Numeric drift on long-lived totals is a good detail to raise.
Own the guidance for the team: default to the smallest state that answers the question, and treat every extra derived value as a maintenance liability paid in defects, not just in bytes.
## What "window state" is A sliding window walks a contiguous span across a sequence. The point of the pattern is that you never recompute the answer for the span from scratch — you keep a small **summary of the current window** and repair it as one element enters and another leaves. Recomputing over a window of width `w` costs `O(w)` per position, so `O(n*w)` overall; repairing costs `O(1)` per move, so `O(n)` overall. The whole speedup lives in that summary, which is why choosing it correctly is the first decision of every window problem, not an implementation detail. ## The two questions that decide the state **1. Is the aggregate reversible?** When an element leaves, can you undo its contribution knowing only the element and the current summary? A total can: subtract the value. A count of elements satisfying a fixed per-element test can: subtract one if the leaver satisfied it. A maximum cannot — removing the current maximum tells you nothing about what the new maximum is, because the summary discarded the runners-up. Non-reversible aggregates need a state that retains candidates, which is a different pattern with its own structure. **2. Does the answer depend on identities or only on a total?** "How many hours" collapses every record into one number. "How many different certifications appear" cannot collapse, because two records with the same tag must count once and two records with different tags must count twice — the summary has to remember *which* keys are in, not just how many records are in. ## The three tiers of state | Window state | Answers questions like | Time per move | Space | |---|---|---|---| | One scalar | total hours, average hours, how many shifts exceed a threshold | O(1) | O(1) | | Count per key | how many distinct tags, is any tag repeated, at most k distinct | O(1) expected | O(distinct keys inside) | | Count per key plus a match counter | does the window contain every required tag | O(1) expected | O(distinct keys inside) | The third tier exists because "contains everything required" is a predicate over the whole requirement set. Recomputing it by walking the requirements each move is linear in the requirement count; keeping one integer that says how many requirements are currently satisfied makes the validity test a single comparison. That integer is derived state, and it is maintained only when a key crosses its required count — never on every occurrence. ## Why "always keep the map" is a weak default The usual defence is that a map lookup is constant time, so the asymptotics are the same. Three things are wrong with treating that as the end of the argument. **Per-operation cost is expected, not guaranteed.** Hash-based lookups are `O(1)` expected and amortized; adversarial or unlucky key distributions degrade them, and every window move performs at least two of them where a scalar performs one addition. **Space is not `O(1)`.** The map holds one entry per distinct key currently inside the window. For a low-cardinality key space that is a handful of entries; for a stream where keys are near-unique it is proportional to the window width, which can dominate the memory of the whole sweep. **Every derived value is an invariant you now own.** A distinct-count kept next to a map has to be repaired at exactly the right moments; getting that wrong produces a window that is quietly judged valid or invalid at the wrong times, and the bug survives any test whose input has no repeated keys. Extra state is a maintenance cost paid in defects, not only in bytes. ## Two practical caveats **Numeric drift.** A running total maintained by repeated addition and subtraction over a long stream accumulates rounding error when the values are floating point. Keeping the total in exact integer units — minutes rather than fractional hours — removes the problem; if that is impossible, recompute the total periodically from the window contents. **Small fixed key spaces.** When the set of possible keys is small and known in advance — six certification tags, say — a fixed array of counts indexed by tag ordinal beats a general map on both memory and constant factor, and makes a full comparison across all keys cheap enough that the derived counter may not be worth its invariant. ## The rule Pick the smallest state that answers the question being asked, and be able to say out loud which of the two tests — reversibility and identity-dependence — forced you up a tier.
- You need the number of shifts in the window that ran longer than eight hours. Scalar or map?Scalar. The test is per-element and fixed, so each record contributes 0 or 1 independently of every other record: add one when a long shift enters, subtract one when a long shift leaves. Identities never matter, and nothing has to be remembered about elements already counted. One integer is the entire state.
- The window keeps a running total of hours as a floating-point number over millions of records. What goes wrong?Rounding error accumulates. Each addition and subtraction rounds, and because elements are added and later removed, the errors do not cancel — the total slowly drifts away from the true sum of the window's current contents. Store the total in exact integer units such as minutes, or periodically recompute it from the window, accepting one linear pass.
- There are only six possible skill tags in the whole system. Does that change the state you pick?Yes. With a small fixed key space, a six-slot array of counts indexed by tag ordinal replaces the map: no hashing, contiguous memory, trivially resettable. It also makes a full scan across all six counts cheap, so a separately maintained derived counter may not earn the extra invariant it introduces.
A tally counter on the door tells you how many people are in the room, but never whether the fire warden is one of them. That gap is the difference between a running sum and a per-key map.
saying these in an interview costs you the question
- Just always keep the map, the complexity is the same anyway
- Map operations are O(1) so the map costs nothing
- Every aggregate can be repaired by subtracting the leaving element
- A distinct count is just additions minus removals
- Averages need a map because they need every value