vault

Monotonic Deque

22 min read

Monotonic Deque

A monotonic deque is a double-ended queue whose contents are kept in monotonically increasing or decreasing order from front to back. It is the natural generalization of Monotonic Stack to settings where elements can leave the structure not only by being “displaced by a larger competitor” (back-end pop, like a monotonic stack) but also by expiring — falling out of a moving window from the front. With this twin-ended behavior, a monotonic deque answers the question “what is the maximum (or minimum) value in the current sliding window of size k?” in O(n) total across the entire stream — beating the heap solution at O(n log k). The pattern is the canonical interview answer for LeetCode 239 (Sliding Window Maximum) and underlies a deep family of problems including LeetCode 862, 1438, 1696, 918, and 1499. The amortized “each element enters and leaves the deque at most once” argument that makes it O(n) is the same argument that powers Monotonic Stack, extended to a structure with two mutating ends instead of one.

1. Intuition — A Lookout Tower with a Strict Hierarchy and a Dismissal Clock

Picture a defensive watchtower in a medieval city. At any moment, soldiers stand in a line on the parapet from front (most senior visible) to back (most junior visible). Two rules govern who’s on the parapet:

  1. Hierarchy rule (back-end pop): when a new soldier is sent to the parapet from the barracks, all soldiers already on the parapet who are junior to the newcomer must immediately step down — they’re outranked and therefore unnecessary; the newcomer will outshine them anyway. The newcomer takes the back of the line. After this, the line’s seniorities are strictly decreasing front to back.

  2. Dismissal-clock rule (front-end pop): each soldier serves a fixed-length watch (size k). When a soldier’s watch ends, they step down from the front, regardless of seniority — the clock is absolute. The most senior soldier still on watch is therefore always at the front (rule 1 ensures the front is most senior; rule 2 evicts when the timer expires).

At any moment, the question “who is the most senior soldier currently on watch?” is answered in O(1) by reading the front of the line. Across the entire night, every soldier is added to the line at most once and removed at most once — the total work is bounded by the number of soldiers, regardless of how many “step-down cascades” happened.

This is exactly a monotonic deque tracking the maximum of a sliding window of size k. The “soldiers” are the array’s elements; “seniority” is value; the “watch length” is the window size; “on watch” means “still inside the current window.”

A second analogy useful for the maximum-tracking variant: a leaderboard of athletes that displays only the currently tied-for-or-leading and recently-set records. A new world-record demolishes all previously-displayed lower records (back-end pops). A record older than the season’s cutoff date drops off the front automatically (front-end expiry).

The deep reason this gives O(n) instead of O(n log k): the Binary Heap-based solution treats every window-exit independently, costing O(log k) per insertion/deletion. The monotonic deque exploits the fact that most elements in a window are dominated and will never be the answer; it discards them eagerly at insertion time, so the structure stays small and operations stay O(1) amortized. It’s an example of “lazy deletion done eagerly” — the heap-based version uses lazy deletion (skip stale elements when they bubble up) and pays log-factor; the deque version commits to deleting on entry rather than on exit and gets the log-factor back.

2. Tiny Worked Example — Sliding Window Maximum, k = 3

arr = [4, 2, 1, 5, 3, 6, 8, 0, 7], window size k = 3. Expected output (max in each window of 3 consecutive): [4, 5, 5, 6, 8, 8, 8].

The deque holds indices (not values — we need indices to know when an entry has expired) in strictly decreasing value order from front to back. At each step:

  1. Expire: while the front index is ≤ i - k, pop from the front.
  2. Maintain hierarchy: while the back’s value is ≤ arr[i], pop from the back.
  3. Push: append i to the back.
  4. Record: once i ≥ k - 1, the answer for the window ending at i is arr[deque[0]].

Trace (deque shown as [idx(value), ...], front first):

iarr[i]ExpirePop back while ≤ arr[i]PushRecord (when i ≥ 2)
04—empty[0(4)]—
12front 0 in windowback 4 > 2, no pop[0(4), 1(2)]—
21front 0 in windowback 2 > 1, no pop[0(4), 1(2), 2(1)]arr[0]=4
35front 0 falls out (0 ≤ 3-3=0), pop1: 2≤5 pop; 2: 1≤5 pop; deque empty[3(5)]arr[3]=5
43front 3 in windowback 5 > 3, no pop[3(5), 4(3)]arr[3]=5
56front 3 in window4: 3≤6 pop; 3: 5≤6 pop; empty[5(6)]arr[5]=6
68front 5 in window5: 6≤8 pop; empty[6(8)]arr[6]=8
70front 6 in windowback 8 > 0, no pop[6(8), 7(0)]arr[6]=8
87front 6 falls out (6 ≤ 8-3=5)? 6 > 5, still in window7: 0≤7 pop; 6: 8>7 no pop[6(8), 8(7)]arr[6]=8

Output sequence (i = 2..8): [4, 5, 5, 6, 8, 8, 8]. ✅

Total pushes: 9 (one per index). Total back-pops + front-pops: 5 (indices 0, 1, 2 popped from back; index 3 popped from back; index 4 popped from back). Each index entered at most once and left at most once. Total work O(n).

The naive solution scans each window’s k elements: O(nk) = O(n × k). For n = 10⁶ and k = 10⁴, naive is 10¹⁰ ops; deque is 10⁶ ops. Four orders of magnitude faster.

3. The Pattern Recognition Signal

Reach for monotonic deque when any of these problem shapes appears:

  1. “Find the maximum (or minimum) element in every sliding window of size k.” — LC 239 verbatim. The textbook trigger.

  2. “Compute, for each index, the (max | min) over the last k (or up to k) preceding elements.” — Bounded look-back over a moving range. Includes DP transitions like dp[i] = arr[i] + max(dp[i-1], dp[i-2], ..., dp[i-k]), where the max-over-window can be maintained in O(1) instead of O(k) per step (LC 1696 Jump Game VI).

  3. “Find the longest subarray such that max(subarray) − min(subarray) ≤ limit.” — LC 1438. Maintain two monotonic deques in parallel (one for max, one for min); the diff between deque-fronts gives the current window’s range. Variable-window sliding with two-deque tracking.

  4. “Shortest subarray with sum at least K (with negatives allowed).” — LC 862. Keep a monotonic deque on the Prefix Sums array; the answer for each i is the smallest i - j with prefix[i] - prefix[j] ≥ K. The deque stores prefix indices in strictly increasing prefix-sum order; at each i, pop from the back while prefix[back] ≥ prefix[i] (back is dominated as a future candidate), then pop from the front while prefix[i] - prefix[front] ≥ K (we found an answer ending at i with start at front). This problem with negatives is one of the most beautiful applications — sliding window alone fails because negatives break the predicate’s monotonicity, but a monotonic deque on prefix sums saves it.

  5. “Stream of values; at each step, report the max (or min) of the last k.” — Real-time analytics use case, same algorithm.

  6. “DP on a sequence where the transition is max/min over a bounded window.” — LC 1696 Jump Game VI, LC 1425 Constrained Subset Sum, LC 918 Maximum Sum Circular Subarray (variant).

The inverse signals — when monotonic deque is not the right tool:

  • The aggregate is median, kth-max, or sum over the window — these are not “decompose to one-best” problems. Use Two Heaps Pattern for medians, sorted multisets for kth-max, Prefix Sums for sums.
  • The window is unsized (variable both ends, no length cap) and the predicate is non-monotone — that’s Sliding Window territory plus possibly Hash Table; monotonic deques specifically optimize fixed-size or fixed-direction-bounded windows.
  • You need random access into the window’s history — deques are O(n) in the middle. Use Segment Tree or Sparse Table for arbitrary range-min/max queries.
  • The values can be re-inserted (ages can come back) — monotonic deques assume each value enters once and leaves once.

4. Pseudocode

The maximum-of-window template (the minimum variant flips the comparator):

sliding_window_max(arr, k):
    n := length(arr)
    deque := empty deque of indices                # maintained: arr-values strictly decreasing front→back
    result := empty list
    for i in 0 .. n - 1:
        # Step 1: expire indices that fell out of the window
        while deque is not empty AND deque.front() <= i - k:
            deque.pop_front()
        # Step 2: maintain monotonic-decreasing invariant
        while deque is not empty AND arr[deque.back()] <= arr[i]:
            deque.pop_back()
        # Step 3: push current index
        deque.push_back(i)
        # Step 4: record window's max once window has filled
        if i >= k - 1:
            result.append(arr[deque.front()])
    return result

Why each step is correct:

  • Step 1 removes any index that is too old to still be in the window of size k ending at i. The window covers [i - k + 1, i]; an index j is out-of-window iff j ≤ i - k. Only the front needs to be checked (because the deque is strictly increasing in indices — see invariants below).
  • Step 2 restores monotonicity. If the back’s value is ≤ arr[i], then for any future window containing i, the back is dominated by i and will never be the max — discard it permanently. Repeat until the back is strictly greater than arr[i].
  • Step 3 appends i at the back.
  • Step 4 reads the front, which is now the max of the window: the front is the leftmost (oldest, lowest-index) value strictly greater than every value to its right (by the invariant).

Two invariants (maintained at all times after each iteration):

I1. Index ordering: the deque’s indices are strictly increasing front to back. I2. Value ordering (for max-deque): the deque’s values (under the indices) are strictly decreasing front to back.

I1 follows from always appending the current index i to the back (and never inserting elsewhere). I2 follows from Step 2 — by popping the back while it’s ≤ arr[i], after the pop loop the back is strictly greater than arr[i], so appending i keeps values strictly decreasing.

Variant: minimum-of-window. Replace ≤ with ≥ in Step 2; values are then strictly increasing front to back; the front is the min.

Variant: strict vs non-strict. The choice of < vs ≤ in Step 2 affects what happens with ties. Using ≤ (pop on equality) means the deque holds strictly distinct values; the front is unique. Using < (don’t pop on equality) means ties are preserved; the front is still a valid max. For most interview problems either works.

5. Python Implementations

5.1 Sliding Window Maximum (LeetCode 239)

from collections import deque
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0:
        return []
    dq: deque[int] = deque()                   # holds indices; values strictly decreasing front→back
    result: list[int] = []
    for i, x in enumerate(nums):
        # Expire out-of-window indices from the front
        while dq and dq[0] <= i - k:
            dq.popleft()
        # Maintain monotonic decreasing invariant from the back
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        # Record once the window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

The four steps from the pseudocode map line-for-line. The <= in the back-pop loop discards equal values too — keeping the deque strictly decreasing. Replacing it with < would keep ties; both are correct, just different deque sizes in pathological cases.

5.2 Shortest Subarray with Sum at Least K (LeetCode 862) — Hard Variant

Given an integer array (with possibly negative elements) and an integer K, return the length of the shortest contiguous subarray whose sum is ≥ K, or -1.

The naive sliding window fails on negatives (you can’t shrink-while-valid because a future negative could rescue or violate). The fix: precompute Prefix Sums, then the question is “for each i, what is the smallest i - j (with j ≤ i) such that prefix[i] - prefix[j] ≥ K?” Maintain a monotonic deque of prefix indices in strictly increasing prefix-sum order:

from collections import deque
 
def shortest_subarray(nums: list[int], k: int) -> int:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    dq: deque[int] = deque()                  # holds prefix-array indices, prefix values strictly increasing front→back
    best = n + 1
    for i in range(n + 1):
        # Step A: while deque-front is a valid start (prefix[i] - prefix[front] ≥ k), record and shrink from front
        while dq and prefix[i] - prefix[dq[0]] >= k:
            best = min(best, i - dq.popleft())
        # Step B: while deque-back has prefix ≥ prefix[i], it's dominated: any future i' that satisfies prefix[i']-prefix[back]≥k
        # also satisfies prefix[i']-prefix[i]≥k with smaller length. Pop.
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)
    return best if best <= n else -1

The two pop loops are doing different jobs:

  • Step A is the answer-extraction pop: when an old j already satisfies the K-sum constraint with the current i, record the candidate length i - j and remove j from the deque (any future i' > i would only give worse — longer — answers using the same j, since we want shortest).
  • Step B is the dominance pop: an older j with prefix[j] ≥ prefix[i] is dominated as a future candidate (because using i as the start gives a smaller length and a larger gap to clear K).

Both popping rules combined keep the deque size bounded; each prefix index enters at most once and leaves at most once. Total O(n).

5.3 Jump Game VI (LeetCode 1696) — DP with Bounded-Window Max

Given nums and k, you start at index 0 and at each step jump to any index in [i+1, i+k]. Maximize the sum of values landed on, including start and end. Define dp[i] = max score to reach index i. Recurrence:

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

Naive: O(nk). With monotonic deque maintaining the max of the last k dp values: O(n).

from collections import deque
 
def max_result(nums: list[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq: deque[int] = deque([0])                # indices of dp, values strictly decreasing front→back
    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()
        dp[i] = nums[i] + dp[dq[0]]
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[n - 1]

This is the most general “DP-with-bounded-window-max” speedup pattern. Whenever a DP recurrence has a max (or min) over a bounded suffix of the table, this trick collapses an O(nk) DP to O(n).

5.4 Longest Subarray With Absolute Diff ≤ Limit (LeetCode 1438) — Two Deques

Find the longest contiguous subarray such that max(subarray) - min(subarray) ≤ limit. Maintain two monotonic deques: a max-deque (decreasing) and a min-deque (increasing). Variable-size sliding window: while the current window’s max − min exceeds limit, advance left.

from collections import deque
 
def longest_subarray(nums: list[int], limit: int) -> int:
    max_dq: deque[int] = deque()               # decreasing
    min_dq: deque[int] = deque()               # increasing
    left = 0
    best = 0
    for right, x in enumerate(nums):
        while max_dq and nums[max_dq[-1]] <= x:
            max_dq.pop()
        max_dq.append(right)
        while min_dq and nums[min_dq[-1]] >= x:
            min_dq.pop()
        min_dq.append(right)
        # Shrink from left while max - min > limit
        while nums[max_dq[0]] - nums[min_dq[0]] > limit:
            left += 1
            if max_dq[0] < left:
                max_dq.popleft()
            if min_dq[0] < left:
                min_dq.popleft()
        best = max(best, right - left + 1)
    return best

The deques are now indexed by absolute position (not window-relative), so when the window’s left advances past a deque’s front index, the front gets evicted. This is the same expiration mechanism as LC 239, but driven by a variable left rather than a fixed window length.

6. Complexity — The Amortized O(n) Argument, Two-Ended Version

Time: O(n) total.

The amortized argument extends the Monotonic Stack one (which had only back-end pops) to two-ended pops. Define potential Φ as the current deque size. In each iteration i of the outer loop:

  • The front-pop loop runs f_i times (front-end evictions due to expiry).
  • The back-pop loop runs b_i times (back-end evictions due to dominance).
  • Exactly one push (+1 to size).

Real cost of iteration: 1 + f_i + b_i. Change in potential: +1 - f_i - b_i. Amortized cost = real cost + ΔΦ = 2.

Total amortized cost across n iterations = 2n. Plus a final flush of remaining deque contents (≤ n more pops). Total real cost ≤ 3n = O(n).

Equivalently: each input element is pushed at most once (n pushes total) and popped at most once (≤ n pops total, summed across both ends). Comparisons and assignments are O(1) per push/pop. Total work O(n).

Space: O(k) for the deque. The deque can hold at most k indices simultaneously (any older index has expired). For LC 862 and other variable-window variants, space is O(n) worst-case.

Comparison with the heap approach for LC 239:

ApproachTimeSpaceNotes
Naive (scan each window)O(nk)O(1)Trivial; too slow for k near n
Binary Heap (max-heap with lazy deletion)O(n log n)O(n)Heap can grow to n; pop stale on top
Binary Heap (max-heap with index-tracked deletion)O(n log k)O(k)Requires augmented heap
Monotonic dequeO(n)O(k)Optimal; the canonical answer

The deque wins on time and space among O(n)-space solutions. The heap solution is conceptually clean and generalizes to “kth max” (which the deque doesn’t), so it’s worth knowing both — but for the strict “max in each window” problem, the deque is strictly better and is the answer interviewers expect.

7. Variants and Sub-patterns

7.1 Sliding Window Median, Kth Max, Histogram

The deque trick does not generalize to median or kth-max, because those depend on more than the single dominating element. For median, use Two Heaps Pattern; for kth max, use a sorted multiset (SortedList in Python); for full sliding-window order statistics, use a Segment Tree or Fenwick Tree indexed by value.

7.2 First Negative Number in Every Window (GFG classic)

A specialization: for each window, find the first negative number. Maintain a deque of indices of negative numbers; the front is the answer. Same expiry logic.

7.3 Maximum of All Subarrays of Size K with Threshold

Variants like “count windows where max ≥ T” trivially fold the deque output through a counter.

7.4 Constrained Subset Sum (LC 1425)

dp[i] = nums[i] + max(0, max(dp[i-k..i-1])). Same window-max DP optimization as Jump Game VI, with a small max(0, ...) twist.

7.5 Largest Sum Subarray of Length at Most K (variant)

When the constraint is “length ≤ K” rather than ”= K,” combine Prefix Sums with a sliding-window-min on prefix array. The deque holds prefix indices in increasing prefix-sum order; the answer at index i uses prefix[i] - min(prefix[i-k..i-1]).

7.6 Minimum Window Subarray with Sum > Threshold (LC 209 variant)

For non-negative arrays, plain Sliding Window works. For arrays with negatives, monotonic deque on prefix sums (LC 862-style) is required.

7.7 Equivalent Persistent Structure: Minimum Queue

Mikhail Cherniavski’s “minimum queue” construction implements a queue augmented with O(1) min-query (or max-query) by composing two monotonic stacks. The two-stack-amortized-queue (LC 232) plus the monotonic-stack invariant on each stack gives O(1) amortized push/pop and O(1) min-query, structurally identical in capability to a monotonic deque.

8. Pitfalls

8.1 Storing Values Instead of Indices

You need indices to detect expiry (deque[0] <= i - k). Storing values and tracking the front separately is possible but error-prone; store indices, recover values via arr[deque[0]].

8.2 Off-By-One in the Window-Expiry Check

For a window of size k ending at index i, the window covers [i - k + 1, i]. An index j is outside the window iff j < i - k + 1, i.e., j ≤ i - k. The check is deque[0] <= i - k, not deque[0] < i - k + 1 (equivalent) and not deque[0] < i - k (off by one). Trace by hand on i = k - 1 (first complete window) and i = k (second complete window) to verify.

8.3 Recording Before the Window Is Full

For LC 239, results are recorded only for i ≥ k - 1. Recording earlier produces output for incomplete windows and inflates the array length. Easy to omit and silently ship a wrong-length output.

8.4 Wrong Pop Comparator (< vs ≤)

Using < keeps duplicates; using ≤ discards them. For pure max queries either is correct, but for “how many duplicate maxes?” or “first occurrence of max” the choice matters. Default to ≤ for the simpler invariant of strictly-decreasing values, unless the problem demands tie preservation.

8.5 Forgetting the Front Pop When the Window Slides

If you only do back-pops (the Monotonic Stack pattern), expired elements at the front sit in the deque indefinitely and pollute the answer. Always check the front for expiry before using it. The order — expire first, then push — is part of the invariant.

8.6 Mishandling Negatives in Sliding-Window-Sum Variants

For LC 862 (negatives allowed), naive sliding window fails. The monotonic-deque-on-prefix-sums fix is non-obvious. If the array has negatives and you reach for a sliding window, stop — switch to prefix-sums-plus-deque (or a sorted-multiset approach).

8.7 Confusing With Monotonic Stack

The choice between Monotonic Stack and Monotonic Deque is determined by whether elements expire from the opposite end of where they enter. If you insert at the back and only pop dominated elements from the back (no front-end expiry), you have a monotonic stack. If you also pop expired elements from the front, you have a monotonic deque. The problem statement is the cue: any “sliding window” or “last k” or “bounded look-back” hint means deque.

8.8 Not Using Python’s collections.deque

list.pop(0) is O(n) (see Queue §7.1). A monotonic deque written on a Python list is not O(n) total — it’s O(n²). Always use from collections import deque for monotonic-deque algorithms.

9. Diagram — Deque State Through [4, 2, 1, 5, 3, 6] with k = 3

flowchart TD
    S0["i=0, x=4\nexpire: none\nback-pop: empty\npush 0\nDQ=[0(4)]"]
    S1["i=1, x=2\nexpire: front 0, 0≤-2? no\nback-pop: 4>2 stop\npush 1\nDQ=[0(4), 1(2)]"]
    S2["i=2, x=1\nexpire: 0≤-1? no\nback-pop: 2>1 stop\npush 2\nDQ=[0(4), 1(2), 2(1)]\nWindow [4,2,1] max=4"]
    S3["i=3, x=5\nexpire: 0≤0? yes, popleft\nback-pop: 1: 2≤5 pop; 2: 1≤5 pop; empty\npush 3\nDQ=[3(5)]\nWindow [2,1,5] max=5"]
    S4["i=4, x=3\nexpire: 3≤1? no\nback-pop: 5>3 stop\npush 4\nDQ=[3(5), 4(3)]\nWindow [1,5,3] max=5"]
    S5["i=5, x=6\nexpire: 3≤2? no\nback-pop: 4: 3≤6 pop; 3: 5≤6 pop; empty\npush 5\nDQ=[5(6)]\nWindow [5,3,6] max=6"]
    S0 --> S1 --> S2 --> S3 --> S4 --> S5

What this diagram shows. Each box reports one outer-loop iteration: the index i, the value arr[i], the front-expiry check (with i - k as the threshold; entries with index ≤ i - k get popped from the front), the back-pop cascade (popping every back-end value ≤ arr[i]), the resulting deque (entries shown as idx(value), front first), and the window’s maximum. Notice two key moments: at i = 3, the front entry 0(4) expires and the entire remainder of the deque (1, 2) is dominated by the new value 5, leaving only [3(5)] — a “full clean-out.” At i = 5, again all back entries are dominated, giving [5(6)]. Visually, the deque oscillates between long-decreasing-runs (during a downward stretch of the input) and small-or-empty (right after a new run-maximum). The total number of pushes (6) plus the total number of pops (4 across both ends in this trace) sum to 2n - 2 = 10 — a constant-bounded multiple of n. That’s the amortized O(n) argument made tangible.

10. Common Interview Problems

#ProblemVariant
LC 239Sliding Window MaximumCanonical: max in fixed window
LC 1438Longest Subarray with Abs Diff ≤ LimitTwo deques (max + min)
LC 862Shortest Subarray with Sum at Least KDeque on prefix sums (negatives OK)
LC 1696Jump Game VIDP with bounded-window max
LC 1425Constrained Subset SumDP with bounded-window max + nonneg cap
LC 918Maximum Sum Circular SubarrayVariants combine deque with Kadane
LC 1499Max Value of EquationDeque on (y - x, x) candidates
LC 1944Number of Visible People in a QueueVariant — usually monotonic stack, but illustrative
LC 1124Longest Well-Performing IntervalPrefix sums + monotonic stack/deque trick
GFGFirst Negative in Every Window of Size KSpecialization of LC 239
LC 480Sliding Window MedianNOT monotonic deque — use Two Heaps Pattern (contrast)

11. Open Questions

  • Is there a sub-O(n) algorithm for the offline “max of every window of size k” problem if the input has special structure (e.g., bounded value range)? For the general comparison-based case, O(n) is optimal — every element must be inspected at least once.
  • The “minimum queue” via two monotonic stacks (Cherniavski) achieves the same complexity — when does it outperform the direct deque construction in practice? Cache-locality benchmarks would clarify.
  • For 2D sliding windows (k×k square), the standard approach is to apply a 1D monotonic deque first along rows, then along columns. Is there a direct 2D monotonic-deque construction with better constants?
  • In an online setting with adversarial inputs that force the deque to grow to size k (a strictly decreasing input), is there a way to compress the deque further? Probably not without losing the O(1) amortized push.

12. See Also

Graph View

Backlinks