Monotonic Deque — Algorhythm<br>Monotonic Deque

01 / The one-sentence essence<br>A deque whose values stay monotonic front → back, with two ends doing distinct jobs: the front evicts when a window slides past; the back drops values dominated by an arriving one. The front always holds the window's max in O(1).

animationcomplexity

Problemsliding-window max — one value per windowInput[1, 3, -1, -3, 5, 3, 6, 7], k=3?<br>input<br>10<br>31<br>-12<br>-33<br>54<br>35<br>66<br>77

deque ↔<br>— empty —

result<br>?0<br>?1<br>?2<br>?3<br>?4<br>?5

Slide a window of size k = 3 over the array. Keep a deque of indices whose values are strictly decreasing front → back — the front is always the window's max.

step<br>0 / 39

deque size

windows recorded<br>0 / 6

predict off0.5×1×2×<br>0 / 39

arrayk<br>defaultincreasingdecreasingcascade-dropk=2

02 / The pattern signature<br># sliding-window max — strictly-decreasing deque of indicesdq ← [ ] // deque of indicesfor i in 0..n−1:if dq not empty and dq.front ≤ i − k:dq.popFront() // slid out of windowwhile dq not empty and arr[dq.back] i]:dq.popBack() // dominated; never a future maxdq.pushBack(i)if i ≥ k − 1: result[i − k + 1] ← arr[dq.front]

03 / When to recognize this pattern<br>"max / min of every window"<br>Any phrase that says "for every contiguous window of size k, compute the max (or min)" — the classic shape. A naive scan is O(N·k); the monotonic deque collapses it to O(N).

"per-window summary"<br>The output is one value per window — the same shape as per-index for monotonic stack, but indexed by window position instead.

"shortest subarray such that…"<br>Many shortest-subarray-with-property problems (LC 862, 1425, 1499) reduce to maintaining a monotonic deque of prefix sums or DP values.

"O(N)" expected<br>Same hint as monotonic stack — rules out the naive per-window inner loop. If your subroutine already needs O(1) lookup of "max so far in window," you want a monotonic deque.

04 / Common pitfalls<br>Confusing the two ends.<br>The deque has two jobs — time (front evicts when sliding past), value (back drops when dominated). They look symmetric but use different conditions: dq.front ≤ i − k on the front; arr[dq.back] on the back. Swapping them silently gives wrong answers.

Storing values instead of indices.<br>You need to know when the front value entered the window to evict it. Store indices; look up values via arr[dq.front].

vs ≤ on the back-drop.<br>Strict () keeps duplicates in the deque — fine, but slightly wasteful. Non-strict (≤) drops equals too. For sliding window max either works; for tie-breaking by latest-index, prefer ≤.

Recording before the window is full.<br>The first k − 1 iterations don't yet have a full window — recording during them yields a wrong-length output. Guard with if i ≥ k − 1.

05 / Go practice — on LeetCode<br>medium7<br>01Min Stack— LC 155→02Sum of Subarray Minimums— LC 907→03Grumpy Bookstore Owner— LC 1052→04Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→05Jump Game VI— LC 1696→06Maximum Subarray Min-Product— LC 1856→07Maximum Tastiness of Candy Basket— LC 2517→

hard11<br>01Largest Rectangle in Histogram— LC 84→02Maximal Rectangle— LC 85→03Sliding Window Maximum— LC 239→04Max Stack— LC 716→05Shortest Subarray with Sum at Least K— LC 862→06Subarrays with K Different Integers— LC 992→07Minimum Number of K Consecutive Bit Flips— LC 995→08Constrained Subsequence Sum— LC 1425→09Max Value of Equation— LC 1499→10Number of Visible People in a Queue— LC 1944→11Maximum Number of Robots Within Budget— LC 2398→