Monotonic Queue: Sliding Window Maximum in O(n)

Sliding Window Maximum — LeetCode 239 — hands you an array of up to 10^5 elements and a window of size k that slides right one step at a time, and asks for each window's maximum. The brute force rescans every window: O(nk), and at n = 10^5 with k = 5 × 10^4 that is 5 × 10^9 comparisons. CPython gets through roughly 10^7 interpreted loop iterations per second, so that submission needs something like eight minutes against a time limit measured in seconds. But the runtime is not the offensive part. Consecutive windows share k − 1 elements. Every rescan re-derives facts you had in hand one step earlier and threw away.

The structure that fixes this, the monotonic queue, is not new machinery. It is two invariants this course already teaches, welded together — and seeing the weld is the entire point of this article, because the weld is what lets you recognize the pattern when it hides inside a DP recurrence.

Two rules you already know, one deque

Start with what the monotonic stack got right. When a new element x arrives, any waiting element that is smaller than or equal to x is finished as a candidate: x is at least as large and strictly newer, so in any future window that still contains the old element, x is also present and wins. The old element is dominated. Discard it. That is the pop-while loop, applied at the back of the structure.

The stack version stops there, and that is exactly why it cannot answer window questions: the stack's oldest survivors live forever. A monotonic stack scanning [9, 1, 1, 1, 1] keeps 9 at the bottom until the end of time, even if your window moved past it four steps ago.

So add the sliding window rule at the other end: an index that has slid out of the window is disqualified regardless of its value. Check the oldest survivor — the front — and evict it the moment it expires.

flowchart TD
    MS["monotonic stack rule\ndiscard dominated candidates\n(back door)"] --> MQ["monotonic queue\none deque, both rules"]
    SW["sliding window rule\nexpire elements that left the window\n(front door)"] --> MQ
    MQ --> P239["LC 239: window maxima"]
    MQ --> PDP["LC 1696 / 1425: windowed DP"]
    MQ --> P862["LC 862: increasing deque over prefix sums"]
    style MS fill:#0e7490,color:#fff
    style SW fill:#a855f7,color:#fff
    style MQ fill:#00e5ff,color:#111
    style P239 fill:#22c55e,color:#111
    style PDP fill:#ffaa00,color:#111
    style P862 fill:#ff2e88,color:#111

Picture a queue outside a club with a bouncer at each door. The back-door bouncer ejects anyone weaker than the newest arrival — they were only in line as a fallback, and a stronger, fresher fallback just showed up. The front-door bouncer ejects anyone whose time is up, strength irrelevant. What survives between the two bouncers is a line of people ordered strongest-to-weakest from front to back, every one of them still inside their time limit. The strongest person currently eligible is, by construction, standing at the front.

That is the whole invariant: indices in the deque are increasing, their values strictly decreasing, front to back. Every element of the current window is either in the deque or dominated by something in the deque. So the front is the window maximum, and reading it costs O(1).

Worked problem 1: Sliding Window Maximum (LC 239)

The canonical statement: given nums (up to 10^5 elements, values in ±10^4) and window size k, return the max of each of the n − k + 1 windows.

{ "type": "array", "title": "nums = [1, 3, -1, -3, 5, 3, 6, 7] — slide a k = 3 window", "data": [1, 3, -1, -3, 5, 3, 6, 7] }

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()          # indices; nums[dq[0]] > nums[dq[1]] > ... after eviction
    out = []
    for i in range(len(nums)):
        # 1. Front expiry: the window is [i-k+1, i], so index i-k is out
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. Back eviction: dominated candidates can never be a future max
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)
        # 3. The front is the answer, once the first window is complete
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Trace it on the standard example, nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]:

i	new	front expiry	back evictions	deque (indices)	emit
0	1	—	—	[0]	—
1	3	—	pop 0 (1 ≤ 3)	[1]	—
2	−1	—	—	[1, 2]	nums[1] = 3
3	−3	—	—	[1, 2, 3]	3
4	5	pop 1 (1 ≤ 4−3)	pop 3, pop 2	[4]	5
5	3	—	—	[4, 5]	5
6	6	—	pop 5, pop 4	[6]	6
7	7	—	pop 6	[7]	7

Step i = 4 is the one to stare at. Index 1 (value 3) was the reigning maximum, but it aged out — front door. Indices 2 and 3 (values −1, −3) were younger but dominated by the arriving 5 — back door. One step, three evictions, and the deque is down to a single index that happens to be the new max. This is the worst-looking step in the trace, and it is also the step that pays for the cheap steps around it, which is the next section.

Two details people gloss over. The expiry check is dq[0] <= i - k because the window is [i-k+1, i] — index i-k is exactly one too old. And it can be an if rather than a while here only because the window advances one step per iteration, so at most one index can expire per step. Change either assumption and those choices stop being safe; both come back in the pitfalls section.

Use collections.deque in Python — it is C-backed with O(1) appends and pops at both ends. Simulating it with a list means list.pop(0), which shifts the whole list and is O(n) per call.

Why amortized O(1) is real

The nested while loop makes this look O(nk). It is not, and the argument is worth having cold because interviewers ask for it: each index enters the deque exactly once and leaves at most once.

Appends: exactly n — every index gets appended in its own iteration, unconditionally. Removals: at most n — an index leaves through the back door (dominated) or the front door (expired), but it can only leave a structure it is currently in, and once out it never returns. There is no third door and no re-entry.

Deque operation budget over the whole scan (n = 100,000, k = 50,000; illustrative)

Brute force:        n·k ≈ 5 × 10^9 comparisons
                    CPython at ~10^7 loop iterations/sec  →  ~8 minutes. TLE.

Heap, lazy deletes: ~2n heap ops × log₂(n) ≈ 17 levels ≈ 3 × 10^6 comparisons
                    →  a few seconds in Python. Usually passes.

Monotonic deque:    n appends + ≤ n removals ≤ 2 × 10^5 deque ops (+ n compares)
                    →  well under a second. O(n), and it is not close.

So a single step can cost O(k) — the i = 4 step above cleared all three resident entries, and an adversarial input can force k − 1 back-evictions in one step. The claim is about the total: 2n operations spread over n steps is O(1) amortized per step. You cannot be charged for an eviction that was never funded by an append. If you ever port this pattern to a context with hard per-step deadlines — a real-time loop, not an interview — the amortized bound is the fine print to reread.

Space is O(k): the deque holds at most one full window's worth of indices, and hits that bound only on a strictly decreasing run.

Worked problem 2: the DP payoff — Jump Game VI and Constrained Subsequence Sum

Here is the part most guides skip, and it is the part that earns the technique its slot in an advanced course. LC 239 asks for window maxima directly. The more common disguise is a DP whose transition takes a max over a trailing window:

Jump Game VI (LC 1696). From index i you may jump to any index in [i+1, i+k]; your score is the sum of nums[j] over every index you land on; maximize the score reaching the last index. The recurrence writes itself:

dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1])

With n and k both up to 10^5, evaluating that inner max by scanning is O(nk) — up to 10^10 operations, dead on arrival. But look at what the inner max is: the maximum of a size-k window over the dp array, a window that slides right one step per iteration of i. That is LC 239, running over an array you are producing as you go.

from collections import deque

def max_result(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])                    # indices; dp values decreasing front to back
    for i in range(1, n):
        while dq and dq[0] < i - k:    # too far back to jump from
            dq.popleft()
        dp[i] = dp[dq[0]] + nums[i]    # best reachable predecessor, O(1)
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[-1]

On nums = [1, -1, -2, 4, -7, 3], k = 2 this returns 7 — the path 1 → −1 → 4 → 3. Same three-beat loop as LC 239: expire, read the front, evict the back and append. The only structural change is that the window is [i-k, i-1] (predecessors, not the current window), which flips the expiry comparison to dq[0] < i - k. Note the deque can never be empty at the read: index i-1 was appended last iteration and cannot have expired for any k ≥ 1.

Constrained Subsequence Sum (LC 1425) is the same skeleton with one twist. Pick a non-empty subsequence maximizing the sum, where chosen elements can be at most k apart in the original array. The recurrence is dp[i] = nums[i] + max(0, dp[i-k..i-1]) — the max(0, ·) says you are allowed to start fresh at i rather than extend a negative-scoring prefix.

def constrained_subset_sum(nums, k):
    n = len(nums)
    dp = [0] * n
    dq = deque()
    for i in range(n):
        while dq and dq[0] < i - k:
            dq.popleft()
        best_prev = dp[dq[0]] if dq else 0
        dp[i] = nums[i] + max(0, best_prev)
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return max(dp)

nums = [10, 2, -10, 5, 20], k = 2 → 37, the subsequence [10, 2, 5, 20]. The −10 gets bridged because index 3 can still see dp[1] = 12 inside its window.

The general claim, stated once and worth memorizing: any recurrence of the form dp[i] = max(dp[j]) + cost(i) (or min) where j ranges over a bounded, forward-moving window is a sliding window maximum in disguise, and a monotonic deque evaluates every transition in O(1) amortized — O(nk) becomes O(n). Competitive programmers call this the monotonic queue optimization. The recognition procedure is mechanical:

1. Write the naive recurrence and circle the max/min.
2. Check the index set under it: is it a contiguous range whose endpoints only move forward as i grows? If yes, this pattern applies.
3. Max → deque with decreasing dp values; min → increasing. Expiry bound comes straight from the window definition.

The same deque algorithm exists outside interviews under the name ascending minima — it is the standard way to compute rolling max/min over a data stream, where re-scanning a window of telemetry per tick would be just as wasteful as it is here.

Worked problem 3: Shortest Subarray with Sum at Least K (LC 862)

This one is rated Hard and earns it, because the deque shows up wearing a different coat. Find the shortest non-empty contiguous subarray with sum ≥ k, where n ≤ 10^5, values can be as negative as −10^5, and k reaches 10^9. Return −1 if none exists.

Your first instinct — expand right, shrink left while the sum stays ≥ k — is wrong here, and knowing why matters more than the fix. The two-pointer argument requires the window sum to grow when the window grows. Negative numbers break that: extending the window can shrink the sum, so neither pointer's movement is justified, and the greedy shrink discards optimal answers.

The repair goes through prefix sums. With P[j] = nums[0] + ... + nums[j-1], a subarray (i, j] has sum P[j] − P[i], and the problem becomes: for each j, find the latest i < j with P[j] − P[i] ≥ k. Two deque rules, both slightly re-flavored:

• Back eviction. If a later index has a smaller-or-equal prefix (P[dq[-1]] ≥ P[j]), the earlier candidate loses on both axes: any subarray starting at j is shorter, and it needs no more future sum to hit k. Dominated. Pop it. The deque's prefix values stay strictly increasing — this is the min-flavored deque.
• Front eviction, on success. When P[j] − P[dq[0]] ≥ k, record the length j − dq[0] — and pop the front permanently. Any later j' that also pairs with it would give a longer subarray, so this start index has already done the best it will ever do. This expiry rule is triggered by value, not by position, which is exactly why it must be a while, not an if: one arrival can retire several front entries.

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x

    best = n + 1
    dq = deque()                       # indices into prefix; increasing prefix values
    for j in range(n + 1):
        while dq and prefix[j] - prefix[dq[0]] >= k:
            best = min(best, j - dq.popleft())     # success — retire this start
        while dq and prefix[dq[-1]] >= prefix[j]:
            dq.pop()                               # dominated start point
        dq.append(j)
    return best if best <= n else -1

flowchart LR
    subgraph "prefix sums of nums = [2, −1, 2], k = 3"
      direction LR
      P0["P0 = 0"] --> P1["P1 = 2"] --> P2["P2 = 1"] --> P3["P3 = 3"]
    end
    P2 -.->|"back-evicts P1: later start, smaller prefix"| P1
    P3 -.->|"P3 − P0 = 3 ≥ k: pop front, best = 3 − 0"| P0
    style P1 fill:#dc2626,color:#fff
    style P0 fill:#22c55e,color:#111

On nums = [2, −1, 2] with k = 3: index 2 evicts index 1 from the back (prefix 1 < 2 — a strictly better future start). Then j = 3 finds P[3] − P[0] = 3 ≥ k, records length 3, and retires index 0. Answer: 3, the whole array. The amortized analysis is unchanged — each of the n + 1 prefix indices enters the deque once and leaves at most once, so O(n) total. One porting note: with n = 10^5 values of magnitude 10^5, prefix sums reach ±10^10, past int32 — Python does not care, but the same code in Java or C++ needs 64-bit sums.

Deque, monotonic stack, monotonic queue: three pages, three different things

Learners conflate these constantly, so here is the line drawn explicitly. The deque page describes a container — how a doubly-linked list or ring buffer delivers O(1) pushes and pops at both ends, no opinion about what you store. The monotonic stack page describes a discipline imposed on a stack — one door, dominance evictions only, no concept of expiry. This page is the discipline that needs both doors. A monotonic queue is not a data structure you will find in any standard library; it is a usage pattern for the deque you already have.

	Deque	Monotonic stack	Monotonic queue (this page)
What it is	A container: O(1) at both ends	A discipline on a stack	A discipline on a deque
Ordering invariant	None	Sorted, enforced on push	Sorted, enforced at both ends
Eviction	Whatever you code	Back only: dominated	Back: dominated. Front: expired
Question answered	"give me both ends fast"	Nearest greater/smaller, no window	Max/min of a forward-moving window
Canonical problems	0-1 BFS, palindrome checks	Daily Temperatures, Largest Rectangle	LC 239, LC 862, LC 1696/1425

The diagnostic question that separates the two techniques: does anything ever expire? If every element remains a candidate until dominated — Daily Temperatures, histogram rectangles — stack. If elements age out of eligibility no matter their value — any problem with a window parameter k — queue. And if the problem mentions a window but asks for something other than an extremum, keep reading; the deque may not survive the requirements, which is the last pitfall below.

What breaks

Storing values instead of indices. The front-expiry check needs the age of the front element, and age lives in the index. With values only, dq[0] <= i - k is unwritable, and duplicate values make any workaround ambiguous. This is the single most common way to write a monotonic queue that fails on the second test case. Store indices; recover values as nums[dq[0]].

The expiry off-by-one. LC 239's window at step i is [i-k+1, i], so the front expires when dq[0] <= i - k. Jump Game VI's window is [i-k, i-1], so the front expires when dq[0] < i - k. Same idea, different boundary, and mixing them up produces answers that are wrong only near window edges — the kind of bug that passes the sample and fails hidden tests. Derive the bound from the window definition every time; do not paste it from memory.

if where a while is needed. In LC 239 the window slides one position per iteration, so at most one front index can expire per step and an if happens to work. In LC 862 the front pop is triggered by a value condition, and one arrival can retire several starts — an if silently returns suboptimal lengths. The safe default is while; earn the if with an argument, or do not write it.

< versus <= on back eviction. Evicting equals (nums[dq[-1]] <= nums[i]) is the right default for window max: of two equal values, the newer one expires later, so the older one is pure dead weight. Keep equals (strict <) and the answers are still correct, but the deque carries duplicate runs it never needs — and in DP variants where the deque length feeds another invariant, that slack becomes a real bug rather than waste.

Dropping the max(0, ·) in LC 1425. Extending a negative-best prefix is worse than starting fresh, and the recurrence encodes that with max(0, best_prev). Omit it and every array with a deeply negative region drags all later dp values down — the classic symptom is a correct answer on all-positive inputs and garbage the moment the input dips.

Reaching for the deque when the query is richer than max/min. Sliding window median, k-th largest in a window, sum of the top three — the monotonic queue cannot answer any of these, and not because of a missing trick: back eviction permanently destroys elements those queries still need. A dominated element is irrelevant to the maximum but entirely relevant to the median. For richer window statistics you want two heaps, an order-statistics structure, or the top-k patterns. The deque's power is its forgetfulness; know what you are agreeing to forget.

When to use what

The decision tree is short. If the problem asks for the extremum of a contiguous window that only moves forward — stated outright, or hiding under a max(dp[j]) inside a recurrence — use the monotonic deque; it is O(n), roughly ten lines, and nothing beats it on this exact shape. If there is no window and the question is "nearest greater/smaller," that is the plain monotonic stack — do not pay for a front door you never open. If the ranges are arbitrary rather than sliding — "max of [l, r]" for random l, r — the deque is useless, and you want a sparse table or a segment tree. If the window query is richer than an extremum, it is heaps or ordered structures, per the last pitfall. And the heap deserves one honest sentence even on the deque's home turf: a lazy-deletion max-heap solves LC 239 in O(n log n), and it is the solution you write when you remember that a faster one exists but not how it worked. It passes. Nobody is thrilled.

The interview meta-skill is the recognition step, not the code. The loop is three beats — expire the front, read the front, evict the back and append — and you can rederive it in a minute from the two-bouncers picture. What you cannot rederive under pressure is the sighting: reading dp[i] = max(dp[i-k..i-1]) + nums[i] in Jump Game VI and seeing LC 239 inside it, or reading LC 862's negatives and knowing the plain window is already dead. That is the difference between having solved Sliding Window Maximum once and actually owning the monotonic queue. Own the weld: dominance at the back, expiry at the front, answer at the front — always O(n), because everyone enters once and leaves once.