Introduction to Monotonic Queue Pattern

Mechanism

A monotonic queue is a deque that, on every insertion, evicts elements from its back that can never be useful again — because the new element is both more recent and at least as extreme (larger for a max-tracking queue, smaller for a min-tracking queue) — so the deque stays sorted for free, and its front is always the answer for the current window, retrievable in O(1).

Recognize the pattern

• The problem asks for a running max/min over a sliding window (fixed or variable size) of an array or stream.
• Naively recomputing the max/min per window costs O(n·k), or O(n log n) with a heap.
• Phrasing like "maximum of every window of size k" or "shortest subarray with sum ≥ X" reduces to maintaining an ordered frontier of still-relevant candidates at both ends of a window.
• You never need every past element — only the ones that could still win for some future window.
• Caveat — don't overreach: "next greater element" sounds similar but is not this pattern. NGE is solved with a monotonic stack (LIFO, single end, no window/front-eviction step at all) — a related but distinct sibling technique. Applying this page's deque-with-window-eviction code to NGE will not work; there is no "size k" and nothing is ever popped from the front.

Brute force vs optimal

Brute force: for each of the n − k + 1 windows, scan all k elements for the max. O(n·k) time, O(1) space. For n = 10^5, k = 10^4 that is ~10^9 comparisons — too slow.

Heap: push (value, index) pairs into a max-heap, lazily discard stale (out-of-window) tops. O(n log n) time, O(n) space — correct but pays an unneeded log factor.

Monotonic deque (optimal): keep indices in decreasing value order; drop the front once it exits the window. O(n) time, O(k) space.

Complexity, derived from first principles

Each of the n elements is pushed onto the deque's back exactly once (n pushes). Once pushed, it is removed at most once — either popped from the back when a later, more extreme element evicts it, or popped from the front when the window slides past it, but never both: the first removal takes it out of the deque permanently. So total removals ≤ n, and total deque operations ≤ 2n = O(n). Amortized per element: O(1). Summed over the array: O(n) time. The deque never holds more than k indices at once (stale ones are evicted as the window moves), so space is O(k), plus O(n − k + 1) for the output array if one is required.

Worked example — sliding window maximum

nums = [1, 3, −1, −3, 5, 3, 6, 7], k = 3. Deque stores indices, kept so that nums[deque] is strictly decreasing.

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

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // indices, nums[dq] strictly decreasing
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
            if (dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

Pitfalls

• Storing values instead of indices — you then can't tell when an element has aged out of the window; store indices and look up values via nums[idx].
• Wrong comparison at eviction — using strict < instead of ≤ (or vice versa) changes whether duplicates are kept.
• Forgetting to evict from the front — a stale index whose window has passed will silently return wrong maxima.
• Checking window validity before eviction order — evict from the back first (maintain order), then from the front (maintain window), then read the front; doing it out of order can read a stale value.
• Confusing this with monotonic stack — if the problem has no window/no front-eviction step (e.g. "next greater element"), you likely want a monotonic stack, not this deque pattern.

When to use / when not — trade-offs

Use when you need running max/min over a sliding window (fixed or variable) and can afford O(k) auxiliary space; it is the only O(n) option.

Avoid / alternatives:

• Heap (priority queue): simpler to reason about, but O(n log n) and needs lazy deletion for expired entries; prefer it if the window bounds are irregular or you need k-th max, not just the max.
• Sparse table / sqrt decomposition: better when queries are for arbitrary (not just sliding) ranges with no updates — O(1) query after O(n log n) build, but monotonic queue wins for a strictly moving window.
• Segment tree: use instead if the array is mutated between queries (point updates) — monotonic queue assumes a static array with a moving window and cannot handle updates.
• Monotonic stack: use instead when the problem has no window at all and only needs one-directional lookback/lookahead (e.g. next greater element, largest rectangle in histogram) — no front-eviction logic applies there.

Takeaways

• A monotonic deque discards dominated candidates so the front is always the current extremum — O(1) query after amortized O(1) update.
• Amortized O(n) comes from each index being pushed once and popped at most once — from exactly one end (a later, more extreme value evicts it from the back, or the window slides past it at the front; whichever fires first removes it for good, so it never leaves from both ends). Total pops ≤ n.
• Choose increasing-order deque to track minimums, decreasing-order to track maximums.
• Store indices, not values, so you can detect and evict elements that have exited the window.
• This is a two-ended, window-bound pattern — it is a sibling of, not the same as, the one-ended monotonic stack used for problems like next greater element.
• Degenerate cases as sanity checks: with k = 1 the answer is just the array itself (every window is one element). For a max-queue, a strictly increasing input collapses the deque to size 1 (each arrival evicts everyone before it, so the newest is always the max), whereas a strictly decreasing input evicts nothing from the back and the deque grows toward size k (the leftmost, largest, stays at the front) — two opposite invariants that are handy for eyeballing a buggy implementation.

Recall: Why is the front of a monotonic decreasing deque guaranteed to be the maximum of the current window, and why is it safe to permanently discard a smaller element that appears before a larger one?

Adapted and expanded from LeetCode / classic sliding-window-maximum treatments (e.g., LeetCode 239) and standard competitive programming references on monotonic deques.