Monotonic Deque

TL;DR

A monotonic deque is a double-ended queue you maintain in sorted order — every push from the back evicts smaller (or larger) elements before it lands, so the front is always the extremum of whatever’s currently inside. It’s the data structure that turns sliding-window-maximum from O(n log k) (with a heap) into a clean O(n) scan.

The trick is what you store. You don’t push values, you push indices. That way you can detect when the front has slid out of the current window (front_index <= i - k) and pop it. Every index enters the deque once and leaves once, so the amortised work per element is O(1) — even though any single push can chain-pop a whole tail of stale entries.

If you only ever need a sliding-window sum or count, a plain prefix-sum or counter is simpler and faster. The monotonic deque earns its keep when the aggregate is non-invertible — max, min, or any extremum that you can’t “subtract off” when the window slides.

When to reach for it

Signals that a monotonic deque is the right tool:

• A sliding window of fixed size k (or variable size with a shrink rule) and you need the max or min of each window.
• A constraint like “longest subarray where max - min <= limit” — you need both extremums of the current window simultaneously, which means two monotonic deques.
• Streaming maxima / minima over the last k events, where rebuilding a heap on every step would be wasteful.
• A DP recurrence of the form dp[i] = min(dp[j]) + cost(i) for j in some window of i — the deque holds candidate j indices in monotone dp[j] order.

Signals it’s not the right tool:

• You need the sum or average over the window — use a running sum and add/subtract on the slide. No deque needed.
• The window doesn’t actually slide; you have arbitrary range-max queries on a static array — use a sparse table or segment tree.
• You need the k-th largest, not the largest. That’s a heap or a multiset.

Flavor 1 — sliding window maximum

The canonical problem (LC 239): given nums and window size k, return the max of every length-k window.

from collections import deque

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()   # holds indices; values at those indices are decreasing
    out: list[int] = []
    for i, x in enumerate(nums):
        # 1. evict indices that fell out of the window from the front
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. evict from the back any index whose value is <= x;
        #    they can never be the max while x is in the window
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        # 3. push the new index
        dq.append(i)
        # 4. once we've seen the first full window, record the front
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Worked example. nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3.

The deque holds indices; the value column shows nums[index] for clarity. “Front-popped” means an index slid out of the window; “back-popped” means indices whose values are <= x got evicted before the new push.

Output: [3, 3, 5, 5, 6, 7]. Notice at i = 4 the front-pop fired first (index 1 is now <= 4 - 3 = 1), then 5 chain-evicted both -3 and -1 from the back, leaving the deque clean.

Flavor 2 — two deques: longest subarray with bounded spread

LC 1438: longest contiguous subarray such that max - min <= limit. You need both extremums of the current window at all times, so run two monotonic deques side by side — one decreasing (max at front), one increasing (min at front) — and shrink from the left whenever the spread exceeds limit.

from collections import deque

def longest_subarray(nums: list[int], limit: int) -> int:
    max_dq: deque[int] = deque()   # decreasing values
    min_dq: deque[int] = deque()   # increasing values
    left = best = 0
    for right, x in enumerate(nums):
        while max_dq and nums[max_dq[-1]] <= x:
            max_dq.pop()
        while min_dq and nums[min_dq[-1]] >= x:
            min_dq.pop()
        max_dq.append(right)
        min_dq.append(right)
        # shrink while the window violates the spread 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

Worked example. nums = [8, 2, 4, 7], limit = 4.

At right = 1 the spread 8 - 2 = 6 exceeds 4, so left advances to 1 and index 0 falls out of max_dq. At right = 3, 7 arrives: it evicts 4 from max_dq (since 4 ≤ 7), but in min_dq we keep 2 and 4 because both are strictly less than 7. The new spread 7 - 2 = 5 still exceeds the limit, so left advances to 2 and index 1 slides out of min_dq (min_dq[0] = 1 < 2). Final answer: 2.

Why it works — the invariant

The deque maintains: the values at the indices inside it are strictly monotone, and the front is the extremum of the current window. Two facts keep that invariant cheap.

First, when a new value x arrives, every back-deque entry y <= x is dead forever — y cannot be the max of any window containing x, and it will leave the window no later than x does. Evicting them doesn’t lose information.

Second, every index is pushed exactly once and popped at most once, so the total work across n elements is O(n) — even though one specific iteration might pop a long tail. The amortised cost per step is O(1).

Complexity

• Time: O(n). Each index enters and leaves the deque at most once.
• Space: O(k) — the deque never holds more than k indices simultaneously (older ones are front-popped). For LC 1438 it’s O(n) worst case because the window can grow to the whole array.

Common pitfalls

• Storing values instead of indices. You then have no way to know when the front has slid out of the window. Always store indices; dereference with nums[dq[0]] only when you need the value.
• Forgetting the front-eviction step. If you only ever back-evict, the front will outlive the window and you’ll return stale maxes. Check dq[0] <= i - k (or < left for variable windows) every iteration.
• Wrong comparator direction. For sliding-window-max the deque is decreasing and you back-pop while nums[dq[-1]] <= x. For min, flip both: increasing and pop while nums[dq[-1]] >= x. Mixing them returns the opposite extremum.
• Strict vs non-strict comparison with duplicates. Using < instead of <= keeps older equal values in the deque, which is correct but wastes memory; using <= evicts them, which is also correct and tighter. Pick one and be consistent — the bug surfaces when the answer must be the earliest occurrence of a tied max.
• Recording results before the window is full. Only append to out once i >= k - 1. Otherwise the first k - 1 entries are partial-window maxes, which is almost never what the problem wants.

Where you see this in production

• Video codec rate control. H.264 / H.265 encoders track a sliding-window max of recent frame sizes to enforce HRD (Hypothetical Reference Decoder) buffer constraints; a monotonic deque keeps the running peak in O(1) per frame instead of rescanning the buffer.
• Network QoS shapers. Token-bucket and leaky-bucket implementations in Linux tc and Envoy track the max queue depth over a rolling window to trigger drop / mark decisions; the same deque trick avoids per-packet heap ops on the hot path.
• Market-data tick aggregators. Quote engines (e.g. KDB+, Databento feed handlers) compute rolling 1-minute high / low / VWAP-bound stats per symbol with paired monotonic deques — millions of ticks per second, so the O(1) amortised update is the difference between keeping up and falling behind.
• Observability rollups. Prometheus-style monitoring sidecars that emit per-minute “max latency over the last 5 minutes” gauges keep a monotonic deque per series; the alternative (a min-heap with lazy deletion) is measurably slower at million-series cardinality.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.