Monotonic Deque

A sliding window can maintain a sum in $O(1)$ per step, because adding and removing are both reversible arithmetic. A maximum is not: when the current maximum slides out of the window, you have no idea what the new maximum is, and rescanning the window costs $O(k)$ — back to $O(n \cdot k)$ overall.

The fix is a monotonic deque: a double-ended queue holding indices whose values are kept sorted. The window’s maximum is then always at the front, readable in $O(1)$, and the whole scan stays $O(n)$ because each index is pushed once and popped once.

What you’ll learn

• Why a heap is the wrong tool here, and what a deque gives you instead.
• The “pop from the back while smaller, pop from the front when expired” template.
• The amortised argument that makes an inner while loop still $O(n)$.
• Three real LeetCode problems solved in the browser: 239, 1696, 1438.

The cue

You are looking at a monotonic deque when…

• You need the max or min of a sliding window, not its sum — 239.
• You need “the best dp value within the last k positions” as a DP transition — 1696 and the whole windowed DP family.
• You need both the window max and min at once, usually to test a spread against a limit — 1438, 2762.
• A sum-based window would work, except negative numbers broke the monotonic-sum assumption — 862.

The tell is that the quantity you need is an extremum over a moving range, and the element achieving it can leave the range.

Why not a heap?

A max-heap gives you the maximum in $O(1)$ and inserts in $O(\log k)$ — but it cannot remove an arbitrary element when it slides out of the window. The usual workaround, “lazy deletion”, means leaving stale entries in and discarding them when they surface, which needs (value, index) pairs and gives $O(n \log n)$.

A deque beats it to $O(n)$ by exploiting something a heap ignores: if nums[j] >= nums[i] and j > i, then i can never again be the maximum — j is both bigger and outlives it. So i can be discarded permanently, not lazily. That single observation is the pattern.

The template

monotonic_deque_template.py

from collections import deque
 
 
def sliding_window_maximum(nums, k):
    dq = deque()          # holds INDICES; their values are strictly decreasing
    out = []
 
    for i, x in enumerate(nums):
        # 1. maintain monotonicity: anything smaller than x is now useless
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
 
        # 2. evict the front if it has slid out of the window
        if dq[0] <= i - k:
            dq.popleft()
 
        # 3. the front is the window's maximum
        if i >= k - 1:
            out.append(nums[dq[0]])
 
    return out
 
 
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

Three moves, always in this order: pop the back to restore monotonicity, pop the front to drop expired indices, read the front for the answer.

Store indices, not values

The deque must hold indices. Values alone cannot tell you whether the front has expired — you need dq[0] <= i - k, and two equal values are indistinguishable. Storing values is the most common way this pattern silently breaks.

Why it is O(n) despite the inner while

Each index is appended exactly once and popped at most once, so the total number of deque operations across the entire run is at most $2n$. The inner while can run many times on one iteration, but only by consuming pushes that already happened — it can never run more times in total than there were pushes.

	Time	Space
Rescan the window each step	$O(n \cdot k)$	$O(1)$
Max-heap with lazy deletion	$O(n \log n)$	$O(n)$
Monotonic deque	$O(n)$	$O(k)$

Visual intuition

A deque, not a stack — because entries leave from both ends. Watch the two eviction rules fire independently:

arrayEvict from the back when outclassed, from the front when out of rangeLC 239 · O(n) time, O(k) space

1031-12-3354356677

1from collections import deque2 3def max_sliding_window(nums, k):4    dq = deque()          # INDICES, values decreasing front to back5    out = []6    for i, v in enumerate(nums):7        if dq and dq[0] <= i - k:8            dq.popleft()          # front fell out of the window9        while dq and nums[dq[-1]] <= v:10            dq.pop()              # back can never be the max again11        dq.append(i)12        if i >= k - 1:13            out.append(nums[dq[0]])   # front IS the window max14    return out

k3

setupA monotonic **deque**, not a stack — because entries can leave from *both* ends. The back is popped when a bigger value arrives (it can never be a maximum again); the front is popped when it slides out of the window. That two-sided eviction is exactly what a stack cannot do.

Play‹›1/15⟲

Back eviction: a new value that is bigger AND later makes everything smaller behind it permanently useless. Front eviction: the current maximum has slid out of the window. A stack can do the first and has no answer for the second, which is precisely why this needs a deque.

Complexity

Approach	Time	Space
Recompute max() per window	$O(n \cdot k)$	$O(1)$
Max-heap with lazy deletion	$O(n \log k)$	$O(n)$
Monotonic deque	$O(n)$	$O(k)$

Each index is appended exactly once and removed exactly once across the whole run, so the total deque work is at most $2n$ — the same amortised argument as the monotonic stack. The heap solution is worth mentioning as the more obvious answer before giving the deque, since it shows you know why $O(n)$ is possible.

The variant map

Variant	What changes	Canonical problem
Window maximum	Pop back while value <= x; decreasing deque	239 Sliding Window Maximum
Window minimum	Pop back while value >= x; increasing deque	1438 (paired with a max deque)
Both at once	Run two deques side by side over the same window	1438 · 2762
Windowed DP	The deque holds indices into dp, not nums	1696 Jump Game VI
Prefix sums + deque	Deque over the prefix-sum array to allow negatives	862 Shortest Subarray with Sum at Least K

Practice — real LeetCode problems

LC 239 — Sliding Window Maximum · Hard

Problem. Given an array nums and a window size k, return an array of the maximum value in each window as it slides from left to right.

Constraints. 1 <= len(nums) <= 10^5, 1 <= k <= len(nums), -10^4 <= nums[i] <= 10^4.

Examples. nums = [1,3,-1,-3,5,3,6,7], k = 3 gives [3,3,5,5,6,7] · nums = [1], k = 1 gives [1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The invariant: the deque holds indices in increasing order, whose values are strictly decreasing. Consequently dq[0] is always the index of the window’s maximum.

When a new value x arrives, every index at the back whose value is <= x is permanently useless: x is at least as large and stays in the window longer. Pop them. Then evict the front if it has aged out.

Time $O(n)$ amortised. Space $O(k)$.

Why <= and not <: with <, equal values pile up in the deque. That is still correct (the front remains a maximum) but wastes space. Using <= keeps the deque minimal. Either passes; be ready to justify yours.

Follow-ups you should expect: “Window minimum?” — flip the comparison to >=. “Why not a heap?” — see the note above: a heap cannot evict an arbitrary expired element, so it degrades to $O(n \log n)$. “Can you do $O(1)$ space?” — no; you provably need to remember up to k candidates.

LC 1696 — Jump Game VI · Medium

Problem. You start at index 0 and must reach the last index. 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 (including 0 and the last). Return the maximum score.

Constraints. 1 <= len(nums), k <= 10^5, -10^4 <= nums[i] <= 10^4.

Examples. nums = [1,-1,-2,4,-7,3], k = 2 gives 7 · nums = [10,-5,-2,4,0,3], k = 3 gives 17 · nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The DP is immediate: dp[i] = nums[i] + max(dp[i-k] … dp[i-1]), with dp[0] = nums[0]. Evaluated naively that is $O(n \cdot k)$, which TLEs at $n = k = 10^5$.

The inner max is a maximum over a sliding window of dp — so it is LC 239 embedded in a DP recurrence. The deque holds indices into dp, front = best reachable predecessor.

Time $O(n)$. Space $O(n)$ for dp, $O(k)$ for the deque.

Order matters here in a way it does not in 239: evict the expired front first, then read dp[dq[0]], then push i. Pushing before reading would let i be its own predecessor.

This “max over the last k states” shape is worth memorising — it turns up in constrained-jump, stock-cooldown, and bounded-knapsack problems, and a deque removes the k factor every time.

Follow-ups you should expect: “Greedy instead?” — no, greedy fails because a locally poor landing can be the only route to a large later value. “Can you drop the dp array?” — you only need the last k entries, so a ring buffer of size k gives $O(k)$ space.

LC 1438 — Longest Continuous Subarray With Absolute Diff ≤ Limit · Medium

Problem. Return the length of the longest contiguous subarray in which the difference between the maximum and minimum element is at most limit.

Constraints. 1 <= len(nums) <= 10^5, 1 <= nums[i] <= 10^9, 0 <= limit <= 10^9.

Examples. nums = [8,2,4,7], limit = 4 gives 2 · nums = [10,1,2,4,7,2], limit = 5 gives 4 · nums = [4,2,2,2,4,4,2,2], limit = 0 gives 3

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

This is a longest-valid sliding window whose validity test is window_max - window_min <= limit. Neither extremum is maintainable by arithmetic, so keep one deque for each.

Time $O(n)$. Space $O(n)$ worst case for the two deques.

Evict the front only when it equals left

Inside the shrink loop, max_dq.popleft() must be guarded by if max_dq[0] == left. The element leaving the window is nums[left], and it might not be the current extremum — if it is not, its index is not at the deque front and popping would discard a live candidate. Writing an unconditional popleft() here is the classic bug, and it produces answers that are too large on inputs like [4,2,2,2,4,4,2,2].

A sortedcontainers.SortedList also solves this in $O(n \log n)$ and is a fine thing to mention — but it is not in the standard library, so it is unavailable in many interview environments.

Follow-ups you should expect: “Return the subarray?” — track best_left when best updates. “What if limit were on the sum instead?” — back to an ordinary prefix-sum window. “Count all valid subarrays rather than the longest?” — add right - left + 1 per step (that is LC 2762).

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 862 is the payoff

Sliding Window can only handle “shortest subarray with sum ≥ k” when values are positive. With negatives, build the prefix sums and keep an increasing deque of prefix indices: for each i, pop from the front while prefix[i] - prefix[front] >= k (recording the length), then pop from the back while prefix[back] >= prefix[i]. That is the honest answer to the classic follow-up, and it is pure monotonic deque.

6 problems

0 easy3 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○1438Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitmediumTwo deques over one window; guard the front eviction
• ○1696Jump Game VImediumWindowed DP -- the deque indexes `dp`, not `nums`
• ○2762Continuous Subarraysmedium1438 with `limit = 2`, counting subarrays instead of the longest
• ○239Sliding Window MaximumhardThe base templateNeetCode 150amazongooglebytedance
• ○862Shortest Subarray with Sum at Least KhardDeque over **prefix sums** -- the answer to "what if values are negative?" for LC 209
• ○1499Max Value of EquationhardRewrite the objective so one term is a windowed maximum, then apply the template

Dry run

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Deque holds indices; values in brackets.

i	v	front evicted	back evicted	deque after	output
0	1	—	—	[0(1)]	—
1	3	—	0(1)	[1(3)]	—
2	−1	—	—	[1(3), 2(-1)]	3
3	−3	—	—	[1, 2, 3(-3)]	3
4	5	1(3) out of range	3(-3), 2(-1)	[4(5)]	5
5	3	—	—	[4(5), 5(3)]	5
6	6	—	5(3), 4(5)	[6(6)]	6
7	7	—	6(6)	[7(7)]	7

Output [3, 3, 5, 5, 6, 7].

Step 4 is the one to study: both rules fire in the same iteration. Index 1 leaves from the front because the window has moved past it, and indices 2 and 3 leave from the back because 5 outclasses them. Those are independent mechanisms — conflating them into one condition is the usual way this goes wrong.

Why the deque holds indices and not values

The front-eviction test is dq[0] <= i - k — a position comparison. Store values and there is no way to know whether the front has slid out of the window. This is the same reason the monotonic stack stores indices.

Interview follow-ups

They ask	What they’re checking	The answer
“Why a deque and not a heap?”	Whether you know why, not just what	A heap cannot evict an arbitrary expired element; a deque discards dominated candidates permanently, giving $O(n)$ vs $O(n \log n)$
“Prove it’s $O(n)$”	Amortised analysis	Each index is pushed once and popped at most once, so deque operations total $\le 2n$ regardless of the inner loop
“Why indices and not values?”	Attention to the invariant	Expiry needs positions (dq[0] <= i - k), and duplicate values are otherwise indistinguishable
“Window minimum too?”	Whether the template generalises	Flip the comparison; run both deques together if you need max and min
“What if k changes per query?”	Modelling	The deque is tied to one window width — for arbitrary ranges use a sparse table or segment tree instead

Edge-case checklist

• k = 1 — every window is one element; output equals the input.
• k = len(nums) — one window; the answer is a single global max.
• All equal values — exercises the <= vs < choice; both work but only <= keeps the deque small.
• Strictly increasing input — the deque never exceeds length 1.
• Strictly decreasing input — the deque grows to k; this is the space worst case.
• Negative values only — do not initialise a running best to 0.
• limit = 0 (1438) — valid; only runs of identical values qualify.
• Front eviction guard (1438) — pop the front only when its index equals left.

Self-check

pch.quizTag Monotonic deque — self-check

1. Why a deque rather than a stack?

   A Deques are faster in Python B Entries must be evicted from BOTH ends — from the back when outclassed, from the front when they slide out of the window C A stack cannot hold indices D To keep the values sorted
   pch.quizShowAnswer

   B — Entries must be evicted from BOTH ends — from the back when outclassed, from the front when they slide out of the window — The back eviction is the monotonic-stack rule. The front eviction is new and is what a stack has no mechanism for: the current maximum eventually leaves the window through the far end.

2. Why does the deque store indices rather than values?

   A Indices use less memory B The front-eviction test dq[0] <= i - k is a position comparison, which a stored value cannot answer C Values would break the monotonic order D It makes no difference
   pch.quizShowAnswer

   B — The front-eviction test dq[0] <= i - k is a position comparison, which a stored value cannot answer — Same reason as the monotonic stack. Read values through indices; a bare value cannot tell you whether it has slid out of range.

3. When a new value arrives, why is it safe to discard smaller values behind it?

   A Because they are smaller B Because the new value is both larger AND later, so it survives every window they would have survived — they can never be a maximum again C Because the deque must stay sorted D It is not safe; it is a heuristic
   pch.quizShowAnswer

   B — Because the new value is both larger AND later, so it survives every window they would have survived — they can never be a maximum again — Both properties are needed. Larger alone would not justify it; later alone would not either. Together they mean the discarded values are dominated for the rest of the run.

4. What is the time complexity, and how do you justify it given the inner while loop?

   A O(n·k) — the while loop can run k times B O(n) — each index is appended once and removed once, so total deque operations are at most 2n C O(n log k) — the deque is kept sorted D O(k) — bounded by the window
   pch.quizShowAnswer

   B — O(n) — each index is appended once and removed once, so total deque operations are at most 2n — The same amortised argument as the monotonic stack: bound the total, not the per-iteration work. One iteration may evict five entries and the next none.

Recall card

• Cue — the maximum or minimum of a sliding window, or any window aggregate that cannot be undone by subtraction (max and min cannot; a sum can, which is why a plain sliding window handles sums).
• Invariant — indices in the deque, values decreasing front to back. The front is always the window’s answer.
• Two evictions — back: while the back’s value ≤ the incoming value. Front: if dq[0] <= i - k.
• Complexity — $O(n)$ amortised, $O(k)$ space.
• Remember — store indices; the two eviction rules are independent; start recording output at i >= k - 1.
• Alternative to name — a max-heap with lazy deletion gives $O(n \log k)$; mention it, then give the deque.

Recap

• A sliding window handles sums by arithmetic, but an extremum needs a monotonic deque: indices in, values sorted, extremum at the front.
• Three moves in order: pop the back while dominated, pop the front when expired, read the front.
• Store indices, never values — expiry is positional.
• $O(n)$ amortised: each index is pushed once and popped once, so the inner while cannot exceed the total number of pushes.
• The pattern generalises past arrays: over dp it removes the k from windowed-DP transitions (1696), and over prefix sums it rescues sum-windows from negative numbers (862).

Next: Prefix Sums and Difference Arrays — the other answer to “negative numbers broke my window”, and the $O(1)$ range-query workhorse.