In a rolling-maximum deque over the last k readings, why can an older smaller reading be dropped forever?
answer
- ask who can still win later
- windows only move forward
- compare the newest reading with older ones
- an older, smaller reading is shadowed
- survivors form a decreasing run
basics
~20 sA reading older and smaller than the newest one can never win again: every remaining window that contains it also contains that newer, larger reading. Being dominated, it is evicted from the back and never revisited.
solid answer
~50 sThe deque holds only readings that could still be the answer for some future window. When reading `i` arrives, any candidate already held whose value is `<=` the new reading is dominated: it sits at an earlier position, so every window that still includes it also includes `i`, and the new reading is at least as large. There is no future window in which the older one wins, so it is popped off the back before the new index is appended. What survives is a strictly decreasing run of candidate values, oldest at the front, and that front candidate is the maximum of the current window once out-of-range positions have been dropped from the front. The whole trick rests on windows moving only forward — dominance is permanent, which is what makes throwing readings away safe instead of reckless.
go deeper
Be ready to say in one breath why a reading that is older and smaller than the newest one can never win a later window, and where the answer for the current window sits.
Explain the invariant precisely: positions increase towards the back while values decrease, and the eviction loop restores that before each append. Say what it buys and what it costs.
Defend the invariant against real data — repeated readings, long flat stretches, windows wider than the burst — and explain why discarding readings is safe here rather than a risk to be hedged.
Own the boundary: dominance holds only while queries advance monotonically and only for a single winner. Name that limit before a requirement for arbitrary ranges or a top-three list quietly crosses it.
## The problem this shape of structure solves A collector receives load readings one per tick, and a dashboard must show the peak load over the last `k` ticks after every reading. The obvious implementation rescans the last `k` readings at every step, costing `O(n*k)` over a stream of `n` readings. A monotonic deque replaces that rescan by keeping a shortlist of readings that are still *candidates* to be the answer of some window that has not been reported yet. ## What makes a reading a candidate Windows advance by exactly one position each step, and they never move backwards. Fix two positions `p < q` inside the current window with `reading[p] <= reading[q]`. Any window that still contains `p` starts at or before `p` and has length `k`, so it ends at or after `p`; since `q > p` and `q` is inside the current window, every future window containing `p` also contains `q`. The maximum of such a window is therefore at least `reading[q]`, which is at least `reading[p]`. So `p` can never *be* the reported maximum on its own merits again. It is **dominated**, and dominance is permanent because windows only move forward. That single observation is the whole structure. When reading `i` arrives, walk from the back of the deque popping every candidate whose value is `<=` the new reading — each of those is dominated by `i` — then append `i`. Nothing that could still win is ever discarded, so correctness is preserved; everything that cannot win is discarded, so the shortlist stays small. ## The invariant that results After each append, the deque holds positions in increasing order (they are appended in arrival order) whose readings are strictly decreasing from front to back. Two consequences follow directly: - The **front** holds the largest surviving candidate, so it is the answer for the current window once expired positions have been removed from the front. - Every other candidate is a *runner-up in waiting*: smaller than the front, but newer, so it inherits the title once the front ages out of the window. That second point is what people miss. A reading smaller than everything currently held is **not** useless and must not be skipped: it is appended at the back precisely because the larger candidates ahead of it will expire before it does. ## A trace Readings `9, 3, 2, 1, 7` with window length `k = 3`, deque shown as positions: | step | reading | evictions | deque | reported | |---|---|---|---|---| | 0 | 9 | none | [0] | — | | 1 | 3 | none (9 > 3) | [0,1] | — | | 2 | 2 | none (3 > 2) | [0,1,2] | 9 | | 3 | 1 | none; position 0 expires | [1,2,3] | 3 | | 4 | 7 | drop 3, 2, 1 (all `<= 7`) | [4] | 7 | Step 4 shows dominance doing its job: one large reading wipes out three smaller, older candidates at once. Step 3 shows the other half of the structure — the front leaving because its *position* has aged out of the window, not because a larger reading arrived. ## Where the argument stops Dominance holds only because queries advance monotonically. If the product later needed the maximum over an arbitrary range chosen after the fact, a discarded reading could be the only one in range and dropping it would be wrong; that requires a different structure entirely. Likewise, dominance is about a single winner: it says nothing about the second-largest reading, so a request for the top three in each window is not a small edit to this structure. ## Common wrong answers "You must keep the whole window so you can recompute" — no, only the decreasing run can ever win. "The deque is a sorted copy of the window" — it is a *subset*, and it is ordered by position, with values happening to decrease as a consequence of eviction. "A smaller new reading is useless" — it is the heir apparent. "The maximum could be anywhere in the deque" — it is always at the front, which is exactly what makes the answer `O(1)` to read.
- Where does the current window's maximum sit in the deque, and why there?At the front. Candidates are held oldest-first with values decreasing towards the back, so once aged-out positions are removed from the front, the front candidate is both in-window and the largest survivor. Anything that beat it was itself evicted as dominated earlier.
- What happens when the newest reading is smaller than every candidate currently held?Nothing is evicted and the new position is appended at the back as the smallest candidate. It matters later: once the larger, older candidates age out of the window, this reading may become the window maximum, so discarding it would be wrong.
- Would the same dominance argument survive if queries could reach backwards as well as forwards?No. Dominance relies on a newer position outliving every older one, which is only true because windows advance. If a query could cover a range ending before the newer reading, the older one might be the only candidate in range, and evicting it would produce a wrong answer.
Think of contenders for a title where every bout is scheduled later than the last. The moment a stronger, younger contender shows up, the older weaker one can never hold the belt again — so you can strike them off the list rather than carry them.
saying these in an interview costs you the question
- Says the deque must hold every reading in the window
- Describes the deque as a sorted copy of the window
- Evicts the newer reading and keeps the older larger one
- Skips a new reading because it is smaller than the current peak
- Thinks the maximum can sit anywhere inside the deque