Step-by-Step Monotonic Queue for Sliding Window Maximum

Sliding window maximum is the classic place where a monotonic queue feels like magic. Beginners often copy a snippet without understanding why elements are popped or when indices expire. This article slows the process down with labeled steps, ASCII visuals, and a minimal code template you can adapt in interviews.

TL;DR

• Use a deque that keeps values in decreasing order so the front is always the max of the current window.
• It matters for interviews because you achieve O(n) instead of O(nk) and can explain why the pop rules guarantee correctness.
• Core steps: push new element while popping smaller ones, evict indices that leave the window, read the front as the maximum.
• Beginners often forget to store indices (not values) and miss the eviction step, leading to stale maxima.
• You’ll learn visual traces, the exact push/pop rules, and a code template that stays stable across languages.

Beginner-Friendly Explanation

• Monotonic queue: A deque where elements are kept in decreasing order of value; the head is always the window max.
• Why indices matter: You need to know when an element falls out of the window; storing indices lets you evict correctly.
• Two pop rules:
  • Pop from the back while the new value is greater (maintains decreasing order).
  • Pop from the front if its index is outside the current window.

If you prefer a string-focused sliding window first, revisit the pattern in Sliding Window Template for LeetCode Strings to warm up the mental model.

Step-by-Step Learning Guidance

1) Write the invariants

• Deque values are strictly decreasing from front to back.
• The front index is always inside the current window.

2) Dry run with a small array

Array: [1, 3, -1, -3, 5, 3, 6, 7], window k = 3.

After processing 1,3,-1 (window ends at idx 2): deque holds [3, -1] → max = 3
After idx 3 (-3): pop from back? No. Evict front? No. max = 3
After idx 4 (5): pop -3, -1, 3; deque becomes [5] → max = 5
After idx 5 (3): pop from back? No (3 < 5). Evict front? No. max = 5

3) Formalize the operations

• Push: While deque back value < current value, pop back. Then append current index.
• Evict: If deque front index < i - k + 1, pop front.
• Read: Once i >= k - 1, record deque front as the max.

4) Check edge cases

• Duplicate values: keep indices so stability is preserved.
• Negative numbers: rules stay identical; ordering is still by value.
• Small windows: when k = 1, every element is its own maximum.

Code Example: Monotonic Queue Template

from collections import deque

def max_sliding_window(nums, k):
    q = deque()  # holds indices, not values
    res = []
    for i, val in enumerate(nums):
        while q and nums[q[-1]] <= val:
            q.pop()  # remove smaller values
        q.append(i)
        if q[0] <= i - k:
            q.popleft()  # evict out-of-window index
        if i >= k - 1:
            res.append(nums[q[0]])
    return res

Compare how eviction and ordering are handled here versus the counting technique in Prefix Sum Patterns for LeetCode Beginners; both approaches hinge on keeping constant-time window information.

Practical Preparation Strategies

• Shadow code aloud: Narrate “push, pop smaller, evict expired, read max” every iteration until it’s automatic.
• Index tracing: Annotate arrays with indices; it prevents the classic “stale max” bug.
• Complexity reminder: Write O(n) at the top of your notes to signal that each element enters and leaves the deque once.
• Guided drills: Tools like LeetCopilot can generate adversarial windows (duplicates, negatives, narrow and wide windows) so you can rehearse the pop rules under pressure.
• Link patterns: Map when to use this deque vs the two-pointer flow in Sliding Window Template for LeetCode Strings to avoid overusing complex structures.

Common Mistakes to Avoid

Mistake 1: Storing values instead of indices

Without indices, you can’t evict correctly when the window moves.

Mistake 2: Forgetting to evict expired elements

If the front index is out of window, pop it before reading the max.

Mistake 3: Using `<` instead of `<=` in the pop condition

Using < keeps equal values and can cause unnecessary churn; <= keeps the queue strictly decreasing.

Mistake 4: Delaying reads

Start recording results once you’ve filled the first window (i >= k - 1).

FAQ

• How do I know the queue is correct? If the deque is decreasing and the front index is always inside the window, the front is the max.
• What should I practice first? Run the template on two arrays: one increasing, one decreasing. Notice how many pops occur.
• Is this required for all sliding window problems? No—only when you need maximum/minimum in O(1) per step; simpler windows can use counts or sets.
• Can I adapt this to minimum values? Yes, flip the inequality signs to make the deque increasing.

Conclusion

A monotonic queue for sliding window maximum works because each element is pushed and popped at most once while the deque remains decreasing. With indices, clear pop rules, and steady narration, you’ll walk through interview dry runs confidently and avoid stale maximum bugs.