Deque, lazy-deletion heap, or per-window recompute: how do you pick a rolling-maximum implementation?

## The three candidates, priced honestly | approach | time over n readings | memory | notes | |---|---|---|---| | rescan each window | `O(n*k)` | `O(1)` extra | trivial to read; no invariant to break | | heap with lazy expiry | `O(n log n)` worst case | up to `O(n)` entries | each entry pushed once, popped once; stale entries linger until they surface | | heap keeping exactly the window | `O(n log k)` | `O(k)` | needs deletion by handle, so entries must be tracked | | monotonic deque | `O(n)` total | `O(k)` | amortized; one step may cost `O(k)` | Two details in that table are where candidates go wrong. First, the lazy-expiry heap is *not* `O(n log k)`: it does not remove an entry when the window passes it by, only when that entry reaches the top and is found stale, so the heap can accumulate entries for readings long since departed and its size drifts toward the length of the stream. Getting to `O(n log k)` requires a heap that supports deleting a specific entry, which means carrying handles. Second, the deque's `O(n)` is amortized: the total is linear, but a rising run followed by a spike makes one step proportional to the window. ## What actually decides it **How big is the window, really?** Asymptotics are statements about growth, not about your numbers. At a window of five samples the rescan does five comparisons per reading — comfortably cheaper than the heap's pointer chasing, and competitive with the deque's bookkeeping. The linear structure only pulls decisively ahead when the window is large: at a window of ten thousand over a hundred million readings, the rescan is a trillion comparisons and simply not an option. **Is the stream bounded?** On a long-running collector the lazy heap's memory profile is the operational risk, because it grows with the backlog rather than the window. The deque's memory is bounded by the window by construction, which is the property that matters when the process must run for weeks without attention. **Is the requirement stable?** The deque encodes one specific fact: for a *single* extreme over a *forward-advancing* window, an older smaller reading is permanently irrelevant. Ask for the top three per window, or for readings that can be retracted or corrected after arrival, and the dominance argument no longer applies — a heap or an ordered structure absorbs that change, the deque does not. Knowing which requirements are on the roadmap is a legitimate input to the choice. **Is the guarantee the right shape?** Linear total with an occasional window-proportional step is a throughput guarantee. A batch pipeline absorbs it happily. A path with a hard per-sample deadline needs the tail bounded, and that argues for the per-operation bound of a heap, or for chunking the work. **Who maintains it?** This is the input engineers most often leave out, and at a lead level it is the one you are expected to raise. The deque is short but its correctness lives in an invariant that is invisible to a reader who does not already know it: two ends, two eviction rules, positions rather than values. A change made in a hurry — expiring by value, using a strict comparison where a non-strict one was intended, dropping the report guard — produces plausible output that is subtly wrong, and nothing crashes. If you choose it, buy down that risk deliberately: a comment stating the invariant on the eviction loop, and a randomised property test that checks the fast version against the naive rescan on sequences full of duplicates, flat stretches, and windows of one and of the full length. ## How to present the decision A strong answer sequences the reasoning rather than announcing a winner: measure the current numbers, name the budget the feature must meet, choose the simplest implementation that meets it, and state the trigger — a window size, a sample rate, a memory ceiling — at which you would move to the next one. Keeping the naive version alive as a test oracle is what makes that later migration cheap, because the replacement can be validated against it rather than against a hand-written expectation. The weak answer is "linear beats logarithmic, so the deque": correct arithmetic, absent engineering, and it is exactly the reflex the question is designed to catch.