Monotonic Queue Pattern

Why this pattern matters for LeetCode

Sliding Window Maximum asks for the max in every window of size k as it slides across an array. The naive solution recomputes the max by scanning all k elements at each of the n-k+1 positions: O(n × k). A heap gives O(n log k) but requires lazy deletion as elements leave the window. A monotonic deque maintains a decreasing sequence of candidates so the front is always the current window's max — O(1) per step and O(n) total.

What the Monotonic Queue pattern is

A monotonic queue (deque) maintains a sequence of indices such that the corresponding values are always monotonically decreasing (for max) or increasing (for min). When a new element enters the window: pop from the back all elements smaller (for max) than the new one — they can never be the window max while the new element is present. When elements leave the window: pop from the front if their index is out of the window. The front always holds the index of the current window's maximum.

Reach for Monotonic Queue when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Monotonic Queue

• ✓Sliding Window Maximum — return the max for each window of size k
• ✓Sliding Window Minimum — same logic with a monotonically increasing deque
• ✓Next Greater Element — stack-based variant uses a monotonic decreasing stack
• ✓Largest Rectangle in Histogram — monotonic increasing stack tracks left boundaries
• ✓Jump Game VI — max score in a sliding window of size k using a deque

When NOT to use Monotonic Queue

• ✕The window size changes (variable window) — a deque's fixed-front-removal assumption breaks down
• ✕You need to query arbitrary ranges, not just the current window — use a segment tree or sparse table
• ✕The problem only needs a global maximum — a single variable is enough
• ✕Duplicate handling matters and you need to distinguish identical values by position — track indices, not values

Better alternative: For variable windows use a heap with lazy deletion. For arbitrary range queries use a segment tree or sparse table.

JavaScript code template

Sliding Window Maximum — O(n) time, O(k) space

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // stores indices, front = index of current window max

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    while (deque.length && deque[0] < i - k + 1) {
      deque.shift();
    }

    // Remove from the back all indices with values <= nums[i]
    // (they can never be the max while nums[i] is in the window)
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // The window is full starting at index k-1
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

The deque stores indices in order. The front is always the index of the maximum in the current window. Before adding a new index, remove from the front anything outside the window (index < i - k + 1), and remove from the back anything whose value is ≤ nums[i] — those values can never beat nums[i] for the rest of the window. After k-1 elements, emit nums[deque[0]] as the current window's max.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Initialize an empty deque and an empty result array.
2. 2For each index i from 0 to n-1:
3. 3 Remove from the front: pop indices where deque[0] < i - k + 1 (outside window).
4. 4 Remove from the back: pop indices where nums[back] <= nums[i] (dominated by new element).
5. 5 Push i to the back of the deque.
6. 6 If i >= k - 1, the window is full: push nums[deque[0]] to result.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Daily Temperatures

  Monotonic decreasing stack — pop when a warmer day arrives; the gap is the answer for the popped day.

  Premium→
• Next Greater Element I

  Monotonic stack over nums2: pop when a larger element arrives; that larger element is the next greater.

  Premium→

Coming soon

• Sliding Window Maximum

  The canonical monotonic deque problem — find the max in every window of size k in O(n).

  Coming soon
• Jump Game VI

  DP with a monotonic deque to track the max dp value in the last k positions.

  Coming soon

Common mistakes beginners make

• ✕Storing values instead of indices — you need indices to check if an element has left the window. Store indices and look up nums[index] when comparing or outputting.
• ✕Wrong removal order — remove out-of-window elements from the front FIRST, then remove dominated elements from the back. Doing it in the wrong order produces wrong results.
• ✕Using `<=` vs `<` for back removal — removing elements strictly less than nums[i] is correct for maximum. Using `<` (not <=) keeps duplicates, which is fine but slightly changes when they're evicted.
• ✕Confusing monotonic queue with monotonic stack — a stack only supports push/pop from one end. A deque (double-ended queue) supports push/pop from both ends. Sliding window max requires removing from both the front (expired) and back (dominated).

Monotonic Queue vs Heap for Sliding Window Max

Choose the right tool for the job.

Time and space complexity

Each index is pushed to the deque at most once and popped at most once (either from the back when dominated, or from the front when expired). Total push + pop operations across all n iterations is at most 2n. O(n) total. The deque holds at most k indices at any time (one per window position), so space is O(k).

Frequently asked questions

What is a deque and how is it different from a stack or queue?

A deque (double-ended queue) supports push and pop from BOTH ends: pushFront, pushBack, popFront, popBack. A stack only supports push/pop from one end (LIFO). A queue only supports push to the back and pop from the front (FIFO). The monotonic queue needs both ends: old elements expire from the front, dominated elements are removed from the back.

Why does a decreasing deque give the maximum?

The deque is maintained in decreasing order of values (largest at front). Any element smaller than a new arrival is popped from the back — it can never be the maximum while the larger element is in the window. So the front is always the largest remaining candidate. When the front's index falls outside the window, pop it.

How is this different from a monotonic stack?

A monotonic stack (used in Daily Temperatures, Next Greater Element) only needs removal from one end. A monotonic queue (used in Sliding Window Maximum) needs removal from BOTH ends: dominated candidates from the back, expired candidates from the front. Use a stack for 'next greater' problems; use a deque for sliding window max/min problems.

Why is it O(n) if there's a while loop inside the for loop?

Each element is pushed to the deque exactly once and popped at most once. The inner while loops together remove elements that were previously pushed. Total pops across all iterations ≤ total pushes = n. So the inner loops collectively do O(n) work across the entire outer loop — not O(k) per iteration.