Run it
The deque version with its total push and pop counts against the recompute-every-window version, on an input sized to make O(n) against O(n·k) unmistakable.
Why a heap is not quite enough
The natural first thought is a max-heap. It gives the maximum in O(1), and removing the element that just left the window is the problem — a heap cannot delete an arbitrary element efficiently.
The usual workaround is lazy deletion: push (value, index) and, before reading the top, discard entries whose index has fallen out of the window.
O(n log n), and the heap can grow to n entries. Correct, and worth stating as the intermediate step — then improving on it.
The monotonic deque
Keep a deque of indices whose values are in decreasing order. The front is always the maximum of the current window.
Two rules, applied per element:
Evict from the front if the index there has slid out of the window. Evict from the back while the value there is less than or equal to the incoming value — those elements can never be a maximum again, because the newcomer is at least as large and stays in the window longer.
O(n) time — each index is appended once and popped at most once — and O(k) space, since the deque never holds more than one window's worth of indices.
The second rule is the one that needs justifying, and the justification is short: if a later element is at least as large as an earlier one, the earlier one is dominated. It will leave the window first and it is not bigger, so no future window will ever report it as the maximum. Discarding it loses nothing.
Store indices, not values. The front-eviction rule needs to know when an element entered, and values alone cannot tell you that.
Tracing it
[1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque is shown as values for readability:
| i | num | After back-eviction | Deque | Output |
|---|
| 0 | 1 | — | [1] | — |
| 1 | 3 | popped 1 | [3] | — |
| 2 | −1 | — | [3, -1] | 3 |
| 3 | −3 | — | [3, -1, -3] | 3 |
| 4 | 5 | popped −3, −1, 3 | [5] | 5 |
| 5 | 3 | — | [5, 3] | 5 |
| 6 | 6 | popped 3, 5 | [6] | 6 |
| 7 | 7 | popped 6 | [7] | 7 |
At i = 4 three elements are discarded at once, and the total number of pops across the whole run is still bounded by n — which is the amortisation argument that makes the nested while loops linear.
The observation that does the work
If a[j] comes before a[i] and a[j] ≤ a[i], then a[j] can never be the maximum of any future window — every window containing it from now on also contains the bigger, later a[i]. So it can be thrown away the moment a[i] arrives.
What survives is a decreasing sequence, and its front is the maximum of the current window by construction. No scan is ever needed.
Why indices rather than values
The front must be discarded once it falls out of the window, and that needs its position. Storing values leaves no way to tell an expired maximum from a current one.
The expiry check is dq[0] <= i - k — the front is older than the window's left edge. This is the other place an off-by-one lives, and it is worth writing out the first window's indices to check it.
Why it is O(n), not O(n·k)
The inner while can pop several entries in one iteration, which looks quadratic. But each index is pushed exactly once and popped at most once across the entire run, so the total pops are bounded by n.
The alternatives are worth naming: recomputing max per window is O(n·k), and a heap is O(n log k) and needs lazy deletion because you cannot remove an arbitrary element. The deque beats both.
Details that matter
<= or < in the back-eviction? Both give correct maxima. Using <= discards equal values and keeps the deque smaller; using < retains duplicates, which matters only if you need to know how many copies of the maximum are present. For this problem, <=.
Why if i >= k - 1? The first complete window ends at index k−1. Emitting earlier reports maxima of partial windows — which is sometimes the requirement, so it is worth confirming.
The output length is n - k + 1. Checking that is a fast way to catch off-by-one errors.
What if k > n? There is no complete window. Return an empty list, or the maximum of everything — ask rather than guess.
What if k = 1? The output is the input, and the code handles it: each element evicts its predecessor immediately.
The pattern beyond this problem
A monotonic deque or stack applies whenever a problem asks for an extreme value over a moving range, or for the "next greater/smaller" element.
| Problem | Structure | Order |
|---|
| Sliding window maximum | Deque | Decreasing |
| Sliding window minimum | Deque | Increasing |
| Next greater element | Stack | Decreasing |
| Daily temperatures | Stack | Decreasing |
| Largest rectangle in histogram | Stack | Increasing |
| Trapping rain water | Stack | Decreasing |
| Shortest subarray with sum ≥ k (with negatives) | Deque | Increasing prefix sums |
| Jump game with a bounded jump | Deque | Decreasing DP values |
The shared shape: maintain a structure in which elements that can never again be the answer are discarded immediately. Once that is the framing, deciding which side to evict from and in which order follows from the specific question.
Constrained-DP problems are where this earns the most. "Maximum sum of a subsequence with no two elements more than k apart" is a DP whose recurrence needs a window maximum of previous states — the deque turns O(nk) into O(n).
Alternatives worth naming
Sparse table or segment tree. O(n log n) preprocessing and O(1) or O(log n) per query. Overkill here, since the windows are contiguous and only slide forward, and the right answer when queries are arbitrary ranges instead.
Two-pass block partitioning. Split the array into blocks of size k, compute prefix maxima within each block from the left and suffix maxima from the right, and every window's maximum is the max of two precomputed values. O(n) time, O(n) space, and no deque — an elegant answer that surprises interviewers.
max() per window. O(nk), and genuinely the right choice when k is small and clarity matters.
What it is testing
Do you get past O(nk)? Naming the naive approach and its cost is the correct opening; stopping there is not.
Can you justify the back-eviction? "A smaller element that leaves the window earlier can never be a maximum again" is the sentence the interviewer wants to hear.
Do you store indices? Storing values makes window expiry undetectable.
Do you see why nested while loops are still O(n)? Each index is pushed once and popped once.
Do you handle the output offset? Emitting only from index k−1 onwards, and knowing the output has n - k + 1 entries.
Do you recognise the family? Sliding-window minimum, next-greater-element and histogram problems all use the same structure.
Recap in one screen
- Keep a deque of indices whose values decrease; the front is the window maximum.
- Evict from the front when the index expires, and from the back while the incoming value dominates.
- Each index enters and leaves once, so the nested loops are O(n) overall; space is O(k).
- Start emitting at index k−1; the output length is
n - k + 1. - The same monotonic structure solves next-greater-element, daily temperatures and histogram rectangles.