What Is a Monotonic Queue? The O(n) Pattern Behind Sliding Window Maximum

You have an array. A window of size k slides across it, one step at a time. At each position, you need the maximum element inside the window.

The obvious approach scans all k elements at every step. That's O(n·k). When k is 3, fine. When k is 500,000 and n is a million, you just wrote an algorithm that submits to LeetCode, watches the progress bar fill halfway, and gets a polite "Time Limit Exceeded." Twice. While you wonder if maybe you miscounted the constraints.

A monotonic queue solves this in O(n). Every element enters the structure once and leaves once, no matter how large the window gets.

Two Rules, Two Ends

A monotonic queue is a deque (double-ended queue) whose contents are always maintained in monotonically increasing or decreasing order. The "queue" part means elements can enter and exit from both ends. Two ends. Two rules. Elegant and a little smug about it.

Before you add a new element to the back, you evict anything from the back that's now irrelevant. For a maximum query, that means evicting elements smaller than the incoming value. Those smaller elements are dead weight. If the window ever reaches their position, the new element is still there and it's larger. They can never be the answer. They are fired.

At any moment, the front of the deque holds the maximum of the current window.

When the window slides forward, check the front. If the element there has moved outside the window bounds, evict it too.

Back eviction: incoming element beats existing ones. Remove them, they're obsolete.
Front eviction: the front element has exited the window. Remove it, it's expired.

The deque is basically a bouncer that also throws out the old regulars when their membership lapses.

Sliding Window Maximum, Step by Step

Take nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. This is LeetCode 239, the canonical monotonic queue problem.

Expected output: [3, 3, 5, 5, 6, 7].

The deque stores indices, not values. Indices let you check whether a front element has fallen outside the window. This trips people up. You want to compare index 1 to the window boundary, not value 3.

i=0, val=1. Deque empty. Push 0. Deque: [0]

i=1, val=3. Back is index 0 (val=1). 3 > 1, evict. Push 1. Deque: [1]

i=2, val=-1. Back is index 1 (val=3). -1 < 3, keep. Push 2. Deque: [1, 2]. First window complete. Front is index 1 (val=3). Output: 3.

i=3, val=-3. Back is index 2 (val=-1). -3 < -1, keep. Push 3. Deque: [1, 2, 3]. Front is index 1, still inside the window. Output: 3.

i=4, val=5. 5 beats index 3 (val=-3), 2 (val=-1), and 1 (val=3). All evicted in one sweep. Push 4. Deque: [4]. Output: 5.

i=5, val=3. 3 < 5, keep index 4. Push 5. Deque: [4, 5]. Output: 5.

i=6, val=6. 6 beats index 5 (val=3) and index 4 (val=5). Push 6. Deque: [6]. Output: 6.

i=7, val=7. 7 beats index 6 (val=6). Push 7. Deque: [7]. Output: 7.

Final: [3, 3, 5, 5, 6, 7]. Correct. Every element processed once, the window tracked automatically, and zero extra scans.

Why It's O(n), Not O(n·k)

Here's the accounting that actually matters. Each index enters the deque exactly once. Each index exits at most once, from either the back or the front. It can't exit twice. It can't re-enter.

Total work: O(n), regardless of k.

Space is O(k) because the deque holds at most k indices at any time. The monotonic queue pays O(k) space to eliminate the k-factor from time. Compare that to brute force: O(n·k) time, O(1) extra space. Pick your poison, or just pick the one that doesn't time out.

The reason so many people initially reach for a heap here is that O(n log k) feels like an improvement. It is. But O(n) is better. The heap keeps elements around hoping they'll be useful. The deque ejects them the moment they stop being useful. One of these has a philosophy; the other has hubris.

Two Evictions, in Code

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result = []
    dq = deque()  # stores indices

    for i, val in enumerate(nums):
        # front eviction: element has left the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # back eviction: new element is better than existing ones
        while dq and nums[dq[-1]] < val:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

function maxSlidingWindow(nums: number[], k: number): number[] {
    const result: number[] = [];
    const dq: number[] = []; // stores indices

    for (let i = 0; i < nums.length; i++) {
        // front eviction: element has left the window
        while (dq.length > 0 && dq[0] < i - k + 1) {
            dq.shift();
        }

        // back eviction: new element is better
        while (dq.length > 0 && nums[dq[dq.length - 1]] < nums[i]) {
            dq.pop();
        }

        dq.push(i);

        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }

    return result;
}

One caveat on TypeScript: dq.shift() on a plain array is O(k) because it shifts all elements left. For strictly O(n), implement a proper deque with head and tail pointers. In practice, interview judges don't penalize this, and neither should you until the constraints require it.

Minimum Instead of Maximum

Flip the back-eviction comparison. Instead of evicting elements smaller than the incoming value, evict elements larger. The deque keeps elements in increasing order, and the minimum sits at the front.

# back eviction for minimum window
while dq and nums[dq[-1]] > val:
    dq.pop()

Everything else is identical. The structure doesn't care whether it's tracking maxima or minima. You just decide which direction the monotonic invariant points.

How to Recognize This Pattern

The signal: a sliding window combined with a range extreme query (max or min) over that window. Problems rarely announce themselves as "use a monotonic queue." They ask for the maximum in every window of size k and trust that you know the tool. They do not trust this correctly, because most people don't.

Secondary clues:

The brute force is O(n·k), and O(n) or O(n log n) is expected.
You need the largest or smallest element inside a moving range.
The window is fixed-size. (Variable windows use the same structure with a modified front-eviction condition.)

Three problems where this is the intended approach: Sliding Window Maximum (239), Shortest Subarray with Sum at Least K (862), and Constrained Subsequence Sum (1425). Each hides the pattern behind different framing. The deque machinery is the same in all three. If you can trace through 239 without looking anything up, you own the pattern for the other two.

The Stack Solves a Different Problem

Both the monotonic queue and the monotonic stack maintain monotonic order and run in O(n). They are not the same thing, and conflating them in an interview is a solid way to get confused mid-explanation.

A monotonic stack answers "nearest greater or smaller element" problems. You process each element, pop anything dominated from the back, and read the stack top as the answer. No window to manage, so you only need one eviction rule. One end, one rule, simpler life.

The front-eviction rule is what distinguishes the queue. The deque tracks which elements are still alive inside the window. The stack has no equivalent because there is no expiring boundary. Nothing in the stack ever "leaves the window" because there is no window.

If a problem asks for the next greater element per index, use the stack. If it asks for the maximum per window position, use the queue. The back-eviction logic is nearly identical between them. Front eviction belongs only to the queue.

You can read more about the monotonic stack variant in this post on the monotonic stack and deque.

Monotonic Queue vs Heap

A max-heap supports O(log k) insertion and removal. Over n window positions, that's O(n log k). Better than O(n·k). Not as good as O(n).

The queue wins because it discards elements proactively. An element that can never be the future maximum is evicted the moment a larger one arrives. The heap keeps everything until it's explicitly popped, like a hoarder that might need that -3 someday. That laziness costs O(log k) per removal.

Use the heap when the window is not contiguous or when you need arbitrary removals from the middle, which the deque doesn't support efficiently. For fixed sliding windows with extreme queries, the monotonic queue is the right choice and your interviewer will notice if you reach for the heap first.

The Queue Always Pairs with the Window

The monotonic queue works alongside the sliding window technique. The window defines the range. The queue answers the question about that range efficiently.

Without the sliding window, you'd scan everything. Without the queue, you'd scan the window at each step. Together they produce O(n) for a family of problems that otherwise resist it. They need each other. It's codependent in the best way.

Practice by tracing the deque manually on a few examples before you write a single line of code. Once you've done it two or three times, the two eviction rules become muscle memory. The "when to do front eviction vs back eviction" question stops being a question. If you want to test that under pressure, SpaceComplexity runs voice-based mock interviews where you explain your reasoning out loud. That's exactly where pattern recognition either holds up or falls apart.