A rolling-maximum deque has a nested eviction loop, so why is the whole scan O(n)?
answer
- count objects, not loop nesting
- how many times can one position enter?
- every entry leaves at most once
- n appends bound the total removals
- the guarantee is over the sequence
basics
~20 sEach position is appended to the candidate list exactly once and removed at most once, so the inner eviction loop performs at most n removals across the entire scan. Total work is linear even though a single step can evict many candidates.
solid answer
~50 sCounting by loop nesting is the wrong instrument; count by object instead. Every position is appended exactly once, at its own step, and once removed it never comes back — so across the whole scan there are at most `n` removals, whatever shape the readings take. That bounds the total cost of the inner eviction loop at `O(n)`, the outer pass contributes another `O(n)`, and the scan is linear. Watch the direction of the claim, though: this is amortized, not per-step. One step can evict a long run of candidates — a steadily rising ramp of load followed by a single spike empties the list in one go, costing `O(k)` for that sample. What is guaranteed is the total over the sequence, which is what a throughput budget cares about. And amortized is not average-case: no distribution over inputs is assumed, so the bound holds for the worst sequence an adversary could send.
go deeper
Recall the counting rule: each position enters the structure once and leaves at most once, so the eviction loop cannot do more than n removals in total across the scan.
Give the accounting argument out loud, then state precisely what amortized does and does not promise about any single step, and how it differs from average-case.
Bring the operational consequence: linear total work with an O(k) worst step is a throughput guarantee, not a per-tick latency guarantee, and say which of the two your workload actually needs.
Decide when an amortized contract is acceptable at all. A batch pipeline absorbs an occasional long step; a hard per-sample deadline may force chunking or a different structure, and that call belongs in the design, not the code review.
## Why the nesting misleads The outer pass visits `n` readings and the inner loop can, on a given step, remove several candidates. Read structurally, that looks like `O(n*k)`. The structural reading is wrong because the inner loop's trip count is not independent of the outer loop's history — every removal it performs is paid for by an append that happened earlier. ## The accounting argument Give each position one token when it is appended to the candidate list. Appending happens exactly once per reading, so exactly `n` tokens are ever issued. Each iteration of the inner eviction loop removes one candidate and spends its token; a removed candidate is never re-appended, so a token is never spent twice. Therefore the inner loop runs at most `n` times *in total across the whole scan*, not per step. Add the `n` iterations of the outer pass and the constant work per step (one append, at most one expiry, one report) and the total is `O(n)`. The same argument written without tokens: *total removals ≤ total appends = n*. Learn to reach for this counting move whenever a loop's body shrinks a structure that only the outer loop grows — it is the standard way to bound eviction-driven algorithms, and reciting it cleanly is most of what this question tests. ## What amortized does and does not promise Three distinctions are worth getting exactly right, because interviewers probe them and the wrong direction is the common failure. - **Amortized is not per-operation.** The claim is about a *total over a sequence*, not about any single step. Concretely, readings that climb steadily for `k` samples and are then followed by one larger reading cause that one step to evict the entire candidate list — `O(k)` work in a single sample. - **Amortized is not average-case.** Average-case analysis assumes a distribution over inputs; amortized analysis assumes nothing and bounds the worst *sequence*. The linear total here holds for adversarial readings, not merely for typical ones. - **The bound is an upper bound.** Saying a step is `O(k)` in the worst case does not mean any real workload exhibits it. On a monotonically decreasing stretch of load, nothing is ever evicted and every step does constant work. ## Space, and the operational reading At the moment the answer is reported, the candidate list holds only positions inside the current window, so it carries at most `k` entries — one more transiently if the expiry check runs after the append. Space is `O(k)` regardless of how long the stream runs, which is what lets the structure sit in a collector processing an unbounded feed of readings. Contrast the rescan approach: it is `O(1)` extra space but `O(n*k)` time, and the choice between them is a real one when `k` is small. The latency reading matters too. `O(n)` total with an `O(k)` worst step is a *throughput* guarantee. On a batch path over a large archive of readings, that is precisely the right contract and the occasional long step disappears into the aggregate. On a path with a hard per-sample deadline, it is not: the tail is what breaks the deadline, and the honest answer is to budget for the `O(k)` step, chunk the work, or choose a structure with a per-operation bound instead. Candidates who quote "amortized `O(1)` per sample" as though it were a latency guarantee have inverted the direction of the claim, which is the single most common error in this area. ## Sanity checks to keep - If `k = 1`, every reading dominates the previous candidate; each step evicts exactly one and the total is still linear. - If the readings strictly decrease, nothing is ever evicted by dominance and the list grows to the window size, draining only through expiry — still linear in total. - If the readings strictly increase, each step evicts exactly one candidate; again linear. The pathological *single step* needs a rise followed by a spike, and it borrows from cheap steps that already happened.
- Which input makes a single step of the eviction loop as expensive as possible, and how expensive is it?A run of readings climbing steadily across the window followed by one reading larger than all of them. That step evicts every candidate — up to `k` of them — so it costs `O(k)`. The scan is still linear overall, because those candidates were appended during the cheap steps just before.
- Does the amortized bound tell you anything about worst-case per-sample latency on a real-time path?No. It bounds the total over a sequence, not any single step, so a per-tick deadline must be budgeted against the `O(k)` step. The structure gives a throughput guarantee, not a tail-latency guarantee — conflating the two is how a deadline gets missed in production.
- How much memory does the structure hold at peak, and why does that matter for a long-running collector?At most a window's worth of positions, since everything outside the window is expired from the front before the answer is reported. Space is `O(k)` no matter how long the stream runs, which is what makes it safe on an unbounded feed where anything growing with the backlog would eventually exhaust memory.
It is like a turnstile: however chaotic the crowd inside, nobody leaves who did not enter, so total exits are capped by total entries no matter how many surge out at once.
saying these in an interview costs you the question
- Calls a nested loop quadratic without counting removals
- Says amortized means the average over random inputs
- Claims every individual step is constant time
- Quotes the amortized bound as a per-sample latency guarantee
- Thinks the candidate list can grow with the stream length