Queues & Monotonic Deques

Review boundary and corrected contracts

Store indices so expiry is independent of value ties. Remove dominated candidates at the back and expired candidates at the front. Both operations have total linear count. Windows require 1 ≤ k ≤ n; returned output is additional O(n−k+1) storage.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Use the queue as the substrate for level-order processing, and own the monotonic deque well enough to write Sliding Window Maximum cold.

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

Watch first

Optional original companion videos (not prerequisites):

• Sliding Window Maximum — NeetCode: focus on why a newer larger value dominates an older one.
• Implement Stack using Queues — NeetCode: compare queue rotation with the two-stack queue exercise.
• Breadth First Search — WilliamFiset: connect FIFO order to unweighted shortest paths.

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 Session 23 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 equally correct and generalises to a left boundary that advances several positions at once.

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(q) for a queue of length q because remaining references shift left. A wide BFS frontier can therefore cause quadratic queue work; a chain with a frontier of size one does not. Use deque.popleft() to keep queue operations O(1).

For level-order traversal of an acyclic binary tree, freeze the current queue length before visiting a level. Newly appended children belong to the next level:

def level_values(root):
    if root is None:
        return []
    q, levels = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left is not None:
                q.append(node.left)
            if node.right is not None:
                q.append(node.right)
        levels.append(level)
    return levels

Each node enters and leaves once: O(n) time, O(width) queue space, plus O(n) returned values. For a general graph, also mark vertices visited when enqueuing so cycles and shared neighbours do not enqueue them repeatedly.

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. Over an indexable array, sum and count are reversible — read and subtract the departing element. A stream still needs a buffer of outgoing values. 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 FIFO behaviour and BFS, implemented with a plain deque, not monotonic dominance pruning.
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 is moving the right boundary backward or the left boundary backward: a previously discarded candidate can become relevant again. Advancing the left boundary alone is safe; expire all indices below the new left boundary with a while. For arbitrary range queries use a range-query structure, or maintain an active-set heap with explicit membership updates and reinsertion when elements re-enter.

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) worst-case time and O(n) storage with lazy expiry; whether it meets a time limit depends on the constraints. A heap maintains a partial parent-child ordering, not a fully sorted window, but it still retains dominated candidates that the deque can discard.

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.

The failure mode I see most often on this problem is a deque that is only ever popped from the back. The code passes every test where the maximum happens to sit near the right edge of each window and fails whenever a large value expires off the left while still sitting at the deque front. Then the reported maximum is a value that is no longer in the window. Test specifically with a large value early and a long tail of small ones — [9,1,1,1,1] with k = 2 — which isolates the expiry rule and nothing else.

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 — timestamps arrive in strictly increasing order. On each ping(t), append t to a FIFO queue, then popleft while the front is below t - 3000, retaining the inclusive interval [t − 3000, t], 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 without an expiry plan. Indices make positional expiry explicit. A value-only variant is also correct if you know the outgoing value and preserve equal candidates with strict dominance (or counts): pop the front only when it equals the outgoing value. Removing ties without counts breaks that variant.

Using a list and pop(0). Correct output, but O(queue length) per removal and potentially 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.

Myth: Sliding window maximum needs a heap, because you need to know the largest element of a set and that is exactly what a heap is for.

Why: A heap maintains a partial ordering that exposes the extreme at its root. The deque additionally exploits a fact the ordinary heap solution does not use: an element that is both older and no larger than another is permanently useless and can be deleted immediately, not merely deprioritised. That aggressive pruning is what drops the complexity from O(n log n) to O(n) and removes the need for lazy deletion of stale entries. The heap solution is correct and worth mentioning as a first pass, but it is doing strictly more bookkeeping than the problem requires.

Steps 1: Over an indexable array, sum and count can be updated by subtracting the departing element without an extra candidate structure. A one-pass stream must still retain the outgoing values, for example in an O(k) FIFO buffer. Max and min additionally need a way to recover surviving extrema.

Steps 2: Because an element that is older than another and no larger will always be accompanied by that larger element in every future window, it can never be the maximum again and is permanently useless.

Steps 3: Because permanently useless elements are deleted on sight, whatever survives is strictly decreasing in value and increasing in index — which is precisely a monotonic deque.

Steps 4: Because the window advances one position per step and indices therefore expire in increasing order, expiry can be enforced by inspecting only the front, in O(1).

Steps 5: Because each index is appended exactly once and removed at most once, total deque operations are bounded by 2n, giving O(n) overall despite unbounded per-step cost.

Steps 6: Testable prediction: on [9,1,1,1,1] with k = 2 the output must be [9,1,1,1]. An implementation missing the front expiry rule returns [9,9,9,9], which isolates that bug and no other.

Picture: A line of people ordered by height, tallest at the front. A newcomer at the back makes everyone shorter than them walk away — they will never be seen again anyway. Meanwhile the person at the front leaves the moment they age out of the window, however tall they were.

Trigger: Fires on maximum/minimum over windows whose boundaries move forward and for which a dominance rule can discard candidates permanently. Non-invertibility alone does not imply a monotonic deque; a sliding median needs different machinery.

Name: Monotonic deque

Gain: O(n) time, O(k) space, no stale entries to clean up, and the minimum variant is a one-character change.

Cost: Two eviction rules operating on opposite ends is genuinely error-prone under pressure; requires the window to advance monotonically.

Name: Max-heap with lazy deletion

Gain: Retains candidates rather than discarding them by dominance. With explicit active-membership tracking it can support deletions not limited to the oldest entry; re-entering elements must be reinserted if previously removed.

Cost: O(n log n) time and O(n) space, since expired entries linger until they reach the top. Every query needs a cleanup loop before it can read the answer.

Name: Block decomposition (prefix/suffix maxima per block of size k)

Gain: O(n) time using prefix/suffix maximum arrays for blocks of size k; a window answer combines at most two block fragments.

Cost: Only works when the window size is fixed and known in advance; does not generalise to variable windows or to streaming input.

Pick: Use the deque for fixed windows or variable windows with nondecreasing left and right boundaries. If the left boundary jumps, use a while expiry loop. For example, after reading [9, 1, 8], moving left from 0 to 2 only expires 9 and leaves 8 as the maximum. But moving the right boundary back from 2 to 1 in [5, 1, 6] would require the discarded 5 again: the usual deque cannot recover it. A segment tree over a retained array supports such arbitrary range queries.

Worked variant — sliding window minimum and the strictness question

The minimum variant is advertised as "flip one comparison", which is true, but there is a second decision hidden in it that reviewers do probe: strict versus non-strict dominance. Here is the full minimum with both choices annotated.

from collections import deque
 
def sliding_window_min(nums: list[int], k: int) -> list[int]:
    dq = deque()                      # holds INDICES, values increasing front->back
    out = []
    for i, x in enumerate(nums):
        # FRONT: expiry. Window at step i covers [i-k+1, i],
        # so index j is dead exactly when j <= i - k.
        if dq and dq[0] <= i - k:
            dq.popleft()
 
        # BACK: dominance. For MINIMUM the sign flips to >=.
        # An index that is older AND no smaller than x can never
        # be the minimum of any future window that contains x.
        while dq and nums[dq[-1]] >= x:
            dq.pop()
 
        dq.append(i)
 
        # Emit only once the first full window exists.
        if i >= k - 1:
            out.append(nums[dq[0]])   # front = minimum of current window
    return out

Why >= and not >? With non-strict eviction, ties are removed, so the deque holds at most one index per equal value and stays shorter. With strict >, equal values are all retained, the deque is longer, and the answer is still correct — the front is the oldest of the tied minima, whose value is identical. So both work here.

The reason to know this: strictness stops being cosmetic the moment the problem asks for the index of the extreme rather than its value, or asks for the multiplicity of the extreme. Counting windows alone does not make the tie choice observable. Then "which of the tied elements survives" is observable, and you must choose deliberately. State the choice out loud when you write it; it is a cheap signal that you know the difference between correctness and coincidence.

Expiry may occur before or after the append, provided it happens before reading the answer. For valid k ≥ 1 the new index i cannot satisfy i ≤ i − k. Thus the maximum code above (append then expire) and this minimum code (expire then append) are both correct, including k = 1. The former can briefly hold k + 1 indices before expiry, still O(k) space.

Memory hook — "back for better, front for older"

The reason this pattern breaks under pressure is that two different eviction rules run on two different ends for two different reasons, and people fuse them. Separate them with one phrase: back for better, front for older.

• Back for better — the back is evicted because something better just arrived. This is a value comparison. It is a while loop, because one strong newcomer can wipe out many weak incumbents at once.
• Front for older — the front is evicted because it got too old. This is an index comparison. It is a single if, because the window advances by exactly one position, so at most one element can age out per step.

Value rule at the back, position rule at the front; while at the back, if at the front. If you catch yourself writing a value comparison against dq[0], you have crossed the wires.

For the container itself the peg is "list pop(0) is a lie" — it looks O(1) and is O(n), because every remaining element shifts down one slot. collections.deque is the standard choice here; a list with a separate advancing head index is another option, but retains consumed entries unless compacted. Repeated front shifts can make a wide BFS quadratic.

What reviewers actually ask

Monotonic deques are a step above the standard rotation, which is exactly why they discriminate: everyone can code BFS, far fewer can defend a dominance argument.

• 239 · Sliding Window Maximum (Hard) — Practice selection. Probing whether you get past the heap. Follow-up: "why is this O(n) when the inner loop is unbounded?" — amortised accounting, each index in once and out at most once.
• 232 · Implement Queue using Stacks (Easy) — Practice selection. Probing amortised versus worst-case reasoning. Follow-up: "what is the worst case for a single dequeue?" — O(n), and that is fine; say amortised O(1), never plain O(1).
• 225 · Implement Stack using Queues (Easy) — Practice selection. The mirror. Follow-up: "can you do it with one queue?" — yes, rotate after each push.
• 862 · Shortest Subarray with Sum at Least K (Hard) — Practice selection. Probing whether you can apply dominance to prefix sums once negatives break the two-pointer window.
• 933 · Number of Recent Calls (Easy) — Practice selection. Probing plain expiry-from-the-front with no dominance rule at all — the degenerate case of today's pattern.
• 1425 · Constrained Subsequence Sum (Hard) — Practice selection. Probing the deque as an accelerator inside a DP recurrence rather than as the answer itself.
• 346 · Moving Average from Data Stream (Easy) — Practice selection. Probing that a running sum needs no monotonic deque, but a one-pass stream still needs a FIFO/ring buffer to remember which value leaves.

The escalation to watch is a boundary moving backward, not merely the left boundary advancing. Left-only shrinking still removes indices in increasing order; a while handles multiple expirations. Right-boundary rollback can expose dominated values that were discarded.

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 remove O(k) candidates in one iteration. Charge each removal to that candidate’s unique earlier append; no assumption about k consecutive zero-pop iterations is needed.

Space: O(k). After expiry the deque holds at most k indices; the append-before-expiry form can transiently hold k + 1. 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, popped from in, pushed to out, and popped from out at most once: at most four elementary stack operations per element. A single dequeue can cost O(n) after n enqueues; any sequence of m operations starting from an empty queue costs O(m) total. Counting only dequeues while ignoring prior enqueues is not the amortised statement.

Self-check (answer follows each question).

Q: State the two eviction rules of the monotonic deque, including which end each operates on.

A: Dominance eviction from the BACK: pop while the value at the back is <= the incoming value, since an older no-larger element can never win again. Expiry eviction from the FRONT: pop while the front index is <= i - k, since it has slid out of the window.

Q: Over an indexable array, why does a sliding-window sum need no candidate structure while a sliding-window maximum does?

A: Sum is reversible — read and subtract the outgoing array value. Maximum is not reversible: when it departs, surviving candidates are needed. A one-pass stream needs an outgoing-value buffer even for a sum.

Q: Why is the expiry check a single if rather than a while?

A: The window advances by exactly one position per iteration, so at most one index can expire per step. A while loop is harmless but unnecessary.

Q: Why store indices rather than values in the deque?

A: In the index-based template, the index directly identifies expired entries. A value alone does not give its position. A separate correct value-only variant knows the outgoing value and preserves ties or counts; do not mix its expiry rule with index-based tie pruning.

Q: What input isolates a missing front-expiry rule, and what wrong output does it produce?

A: A large value followed by small ones, such as [9,1,1,1,1] with k = 2. The correct output is [9,1,1,1]; an implementation missing expiry returns [9,9,9,9] because the stale 9 never leaves the deque front.

Q: Shortest Subarray with Sum at Least K allows negative numbers, so the two-pointer sliding window fails. How does a monotonic deque solve it?

A: Build the prefix-sum array, then maintain a deque of indices with increasing prefix sums. For each i, pop from the front while prefix[i] - prefix[front] >= K, recording the length — those fronts can never yield a shorter valid subarray later. Then pop from the back while prefix[back] >= prefix[i], since a later index with a smaller-or-equal prefix dominates. Negatives break the two-pointer monotonicity but not the dominance argument over prefix sums.

Stretch: true

You can now…

• Reach for a monotonic deque on 'max or min of every window of size k' without first detouring through a heap.

• State the two eviction rules with the correct end, comparison type, and loop form: back-for-better as a while on values, front-for-older as an if on indices.

• Explain why array-based sliding sums need no candidate structure, while extrema need surviving candidates and streams need outgoing-value storage.

• Defend O(n) by amortised accounting rather than by inspecting the inner loop.

• Write the minimum variant by flipping one comparison, and say why strictness is observable only when identity or indices are asked for.

• Say 'amortised O(1)' for queue-from-stacks and name the O(n) worst case that makes the qualifier necessary.

• Distinguish safe left-boundary advancement from backward boundary moves that can revive discarded candidates; use a range-query structure for arbitrary retained-array windows.

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.

• Use collections.deque rather than repeated list.pop(0): front shifts can make a wide-frontier BFS quadratic.

• Array-based sliding sums need no candidate structure; streams still need outgoing-value storage. Sliding maxima need surviving candidates.

• Two eviction rules: dominance from the back (older and no larger is permanently useless), expiry from the front (slid out of the window).

• Store indices. Expiry is positional and a value tells you nothing about where it lives.

• O(n) amortised: each index is appended once and removed at most once, so total deque operations are bounded by 2n.

• Sliding window minimum is the same code with the dominance comparison flipped from <= to >=.

Corrective source notes

• Minimum Stack / Minimum Queue - Algorithms for Competitive Programming — A monotonic queue obtains linear total work by bounding each element’s insertions/removals. Checked 2026-10-07.

• Python deque semantics (CPython v3.14.0) — endpoint operations and list front-shift costs. Rechecked 2026-10-09.

• Python heap invariant (CPython v3.14.0) — a heap is partially ordered, not sorted. Rechecked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.