L18 · Queues & Monotonic Deques

Series: LeetCode — From Basics to Interview-Ready · Session 18 / 65 · Phase 1 · Core patterns

Why this session exists

Sliding Window Maximum is the deque problem. Know it properly and you know the pattern; know only the template and you will fumble the first variant you meet.

The queue itself is almost too simple to spend a session on — first in, first out, and Python hands you collections.deque with O(1) at both ends. But the queue is the substrate under BFS, and BFS is coming in four sessions for trees and later for graphs. Getting fluent with popleft now, including why you must never use list.pop(0), removes friction from every graph problem you will ever write.

The real content is the double-ended variant. A deque lets you remove from the back as well as the front, and that single extra capability turns "maximum of every window" from O(n·k) into O(n). The mechanism is the same insight as the monotonic stack — discard candidates that can never win — but with an extra eviction rule for candidates that have simply expired out of the window. Two eviction rules instead of one is the whole difficulty, and it is why people who can write a monotonic stack cold still stumble here.

Blank-file warm-up

Five minutes, empty file, no notes. Write:

dq holds INDICES, values decreasing front -> back
while dq and a[dq[-1]] <= a[i]: dq.pop()

Then answer in writing: what is the other eviction condition, which end does it operate on, and what index does it compare against?

If you can produce the back-eviction but not the front-eviction, that is today's finding. The front eviction is what makes this a deque rather than a stack, and it is the half that gets forgotten.

Pattern anatomy

The shape that summons this pattern: an aggregate — max, min — over a window that slides one position at a time, where recomputing from scratch is too slow.

The invariant has two clauses, and both must hold after every step:

The deque holds indices, front to back, whose values are strictly decreasing; and every index in the deque lies inside the current window.

Two clauses, two eviction rules:

• Back eviction (dominance): before pushing index i, pop from the back while the value there is <= nums[i]. Justification: any element that is both older than i and no larger than nums[i] can never be the maximum of any future window, because every future window containing it also contains i, which is at least as large and survives longer. It is dominated. Remove it forever.
• Front eviction (expiry): pop from the front while dq[0] <= i - k. Justification: that index has slid out of the window. Its value is irrelevant, however large.

After both evictions, nums[dq[0]] is the window maximum, because the front holds the largest surviving in-window value by the decreasing invariant.

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()                    # indices; nums[...] strictly decreasing front -> back
    out = []
    for i, v in enumerate(nums):
        while dq and nums[dq[-1]] <= v:     # dominance: evict from BACK
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                  # expiry: evict from FRONT
            dq.popleft()
        if i >= k - 1:                      # window is full, emit
            out.append(nums[dq[0]])
    return out

Eleven lines and every one is load-bearing. Three details worth being deliberate about:

<= in the dominance check, not <. With <, equal values both stay, which is not wrong but wastes space and complicates reasoning about duplicates. With <=, only the newest of a run of equal values survives, and since it expires last, that is the right one to keep.

The expiry check needs only a single if, not a while. Each iteration advances the window by one position, so at most one index can expire per step. A while there is harmless but signals you have not thought about it.

i >= k - 1 gates output because the first k - 1 iterations have a partially filled window with no answer to emit.

For minimum instead of maximum, flip the dominance comparison to >=. Nothing else changes.

The plain queue side of the session is much shorter. In Python, use collections.deque and never a list:

from collections import deque
 
q = deque()
q.append(x)        # enqueue, O(1)
val = q.popleft()  # dequeue, O(1)

A Python list's pop(0) is O(n) because every remaining element shifts left one slot. In a BFS over 10^5 nodes that turns a linear algorithm into a quadratic one, and it is a silent performance bug — the code is correct, just too slow.

The cue

How you recognise this from the problem statement:

1. "Maximum/minimum of every window of size k". Diagnostic for the monotonic deque. Write the template.
2. A sliding window where the aggregate cannot be undone. Sum and count are reversible — subtract the departing element. Max and min are not: when the maximum leaves the window you have no way to recover the previous maximum without extra structure. Irreversible aggregate over a sliding window means deque or heap.
3. "Shortest subarray with sum at least K" and similar. These use a monotonic deque over prefix sums, which is the same machinery applied to a derived array.
4. Level order, shortest path in an unweighted graph, "minimum number of steps". These want a plain FIFO queue and BFS, not a deque.
5. "Implement X using Y" — queue from stacks, stack from queues. Structural exercises testing whether you understand amortised analysis rather than any algorithm.

The anti-cue: if the window does not slide monotonically — if it can shrink from either end arbitrarily — the deque's expiry rule breaks, because expiry assumes indices leave in increasing order. A heap with lazy deletion handles that case instead.

Guided solve

Sliding Window Maximum. Given nums and window size k, return the maximum of every contiguous window of length k.

Start with what is wrong with the obvious approaches, because the derivation comes from fixing them.

Recompute each window: O(n·k). At n = 10^5 and k = 10^4 that is 10^9 operations. Dead.

Max-heap of the window: push each element with its index, and on query pop expired entries off the top lazily. O(n log n), which passes, and it is a perfectly respectable answer to give. But it does more work than necessary, because a heap maintains a full ordering of the window when you only ever need the front.

The insight that beats it: most elements in the window can never be the answer, and you can identify them immediately. If nums[j] <= nums[i] and j < i, then j is useless from now on. Any window containing j and extending to the right far enough to matter also contains i; i is at least as large; and i stays in the window strictly longer. There is no future in which j wins. Delete it permanently.

Apply that rule aggressively and what survives is a strictly decreasing sequence — which is exactly the deque. The structure is not designed, it is derived.

Trace nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

• i=0 (1). Deque empty, push. dq=[0] values [1]. Not full yet.
• i=1 (3). Back is nums[0]=1 <= 3 → pop. Push 1. dq=[1] values [3]. Not full.
• i=2 (-1). Back is 3 <= -1 false. Push 2. dq=[1,2] values [3,-1]. Window full: emit nums[1] = 3.
• i=3 (-3). Back is -1 <= -3 false. Push 3. dq=[1,2,3] values [3,-1,-3]. Front is 1, expiry threshold i - k = 0, 1 <= 0 false, keep. Emit 3.
• i=4 (5). Back -3 <= 5 → pop 3. Back -1 <= 5 → pop 2. Back 3 <= 5 → pop 1. Deque empty, push 4. dq=[4] values [5]. Emit 5.
• i=5 (3). Back 5 <= 3 false. Push 5. dq=[4,5] values [5,3]. Emit 5.
• i=6 (6). Back 3 <= 6 → pop 5. Back 5 <= 6 → pop 4. Push 6. dq=[6] values [6]. Emit 6.
• i=7 (7). Back 6 <= 7 → pop 6. Push 7. dq=[7]. Emit 7.

Output: [3, 3, 5, 5, 6, 7].

Watch i=4. One element cleared the entire deque, because 5 dominated everything. That is the same amortised lumpiness as the monotonic stack, and the same accounting applies: each index is appended exactly once and removed at most once, so the total number of deque operations across the run is at most 2n.

Solo timed

15 minutes each, timer visible.

• Implement Queue using Stacks — two stacks, in and out. Push to in; on pop or peek, if out is empty, drain in into out one element at a time, then take from out. Each element moves between stacks at most once, so operations are amortised O(1) despite the occasional O(n) drain — be ready to state that argument, it is the actual point of the exercise.
• Number of Recent Calls — a plain FIFO queue of timestamps; on each ping(t), append t then popleft while the front is below t - 3000, and return the length.

If you finish early, write Sliding Window Minimum by changing exactly one character, and verify on the trace input above.

Common failure modes

Omitting the front expiry check. Produces a maximum drawn from outside the window. Passes many tests. Isolate with [9,1,1,1,1], k = 2.

Storing values instead of indices. Expiry is defined by position, so with values in the deque you cannot tell whether the front has left the window. Indices, always.

Using a list and pop(0). Correct output, O(n) per operation, quadratic overall. Use collections.deque.

Emitting before the window is full. Without the i >= k - 1 gate the output has k - 1 extra leading entries. Easy to spot in the output length; easy to miss when eyeballing values.

Getting the expiry comparison off by one. The window at step i covers indices [i - k + 1, i], so an index is expired when it is <= i - k. Writing < i - k keeps one stale index; writing <= i - k + 1 evicts a valid one.

Wrong dominance strictness for the minimum variant. Flipping to minimum means >=, not <=. Copy-pasting the max version and changing only the output line silently returns the max.

Complexity

Time: O(n). The outer loop runs n times. Each index is appended exactly once. Each index is removed at most once, whether by back eviction or front expiry, and is never re-added. Total deque operations are therefore bounded by 2n. The inner while can run k times in a single iteration, but only after k iterations that ran it zero times — the same amortised accounting as the monotonic stack.

Space: O(k). The deque never holds more than k indices, because expiry removes anything older than the window. The output array is a separate O(n − k + 1), which is required by the problem and not counted as auxiliary.

Compare against the heap solution's O(n log n) time and O(n) space: the heap can hold every element ever pushed, since expired entries are only removed when they happen to surface at the top.

Queue-from-stacks: amortised O(1) per operation. Each element is pushed to in once, moved to out once, and popped from out once — three operations across its whole lifetime, regardless of the interleaving of calls. A single dequeue can cost O(n) when it triggers a drain, but n dequeues can never cost more than O(n) total.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Sliding Window Maximum enters today and deserves a strict grade. Producing the back eviction alone is not a pass — if you had to be reminded of the front expiry, log it hint at best. That rule is half the pattern and it is the half that gets forgotten.