Monotonic Deque: the Window's Maximum
The biggest value in every window
A dashboard shows the highest temperature of the last ten minutes. Every minute one reading arrives and the oldest one expires, and the number on screen has to be the biggest of what's left. That's the sliding window maximum: given an array and a window of k consecutive values that slides one step at a time, report the maximum of every window, n − k + 1 answers in all.
A window's sum was easy (Introduction to Sliding Window): add the value that arrives, subtract the one that leaves. The maximum doesn't work that way. When the biggest value leaves, nothing you kept says what the new biggest is. This lesson's answer is a deque that keeps only the values that can still win, and the same deque goes on to solve four harder problems.
Rescanning every window, and what it costs
The first answer anyone writes: for each window, look at all k values and take the biggest. It's correct and it's O(n·k), because consecutive windows share k − 1 values and the rescan reads them again every time. On our judge, 100,000 random values in C++, against the deque this lesson builds:
| Window k | Rescan each window | The deque |
|---|---|---|
| 10 | 1.25 ms | 1.96 ms |
| 100 | 7.48 ms | 1.65 ms |
| 1,000 | 65.55 ms | 1.62 ms |
| 10,000 | 589.75 ms | 1.61 ms |
At k = 10 the plain rescan is even a little faster (1.25 ms against 1.96), but from there on it grows with k, ten times the window for about ten times the time, while the deque stays flat. With k close to n, the rescan is quadratic. Python shows the same shape, only slower: at k = 1,000, rescanning with max took 2,399 ms against 50 ms for the deque.
The values that can never win
Here's the observation that fixes it. Suppose a value sits at index i, and a later index j holds a value at least as big. Every window still to come that contains i also contains j, because j arrived later and leaves later. So the value at i can never again be the maximum of anything: j beats or ties it in every window it has left. You can throw it away the moment j arrives.
Throw away every such loser and look at what's left in the window: each survivor is bigger than everything after it, so the survivors fall from left to right, and the first one is the window's maximum. Keep them in a deque, as indexes, and each step is three small moves:
- If the front's index has slid out of the window (it's
<= i - k), pop the front. - While the back's value is smaller than or equal to the new value, pop the back: each one is a loser now.
- Push the new index at the back. Once the first window is full, the front is the answer.
Popping on equal values too is safe: the newer copy wins every window the older one could, and keeps the deque strictly falling. The deque holds indexes, not values, because the front has to know when it slides out.
The window's maximum, one arrival at a time — The deque keeps only the values that can still win: losers leave from the back, expired indexes from the front.
The step-through shows all three moves: 12 knocks out two values at once, and the front expires twice, when 12 and then 8 slide out of the window. Here it is in each language. JavaScript has no deque, but it doesn't need one: every index is pushed exactly once, so an array of n slots with a head and a tail index is enough, with no shift() and no wrapping:
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
deque<int> dq; // indexes, their values falling from front to back
vector<int> out;
for (int i = 0; i < (int)nums.size(); i++) {
if (!dq.empty() && dq.front() <= i - k)
dq.pop_front(); // the front slid out of the window
while (!dq.empty() && nums[dq.back()] <= nums[i])
dq.pop_back(); // smaller or equal, and it leaves first: it can never win
dq.push_back(i);
if (i >= k - 1)
out.push_back(nums[dq.front()]); // the front is the window's maximum
}
return out;
}
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indexes, their values falling from front to back
out = []
for i, x in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft() # the front slid out of the window
while dq and nums[dq[-1]] <= x:
dq.pop() # smaller or equal, and it leaves first: it can never win
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]]) # the front is the window's maximum
return out
static int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>(); // indexes, their values falling from front to back
int[] out = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k)
dq.pollFirst(); // the front slid out of the window
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])
dq.pollLast(); // smaller or equal, and it leaves first: it can never win
dq.offerLast(i);
if (i >= k - 1)
out[i - k + 1] = nums[dq.peekFirst()]; // the front is the window's maximum
}
return out;
}
function maxSlidingWindow(nums, k) {
// every index is pushed once, so n slots and two indexes make the deque: no shift(), no wrapping
const dq = new Int32Array(nums.length);
let head = 0, tail = 0; // the deque is dq[head .. tail - 1]
const out = [];
for (let i = 0; i < nums.length; i++) {
if (tail > head && dq[head] <= i - k)
head++; // the front slid out of the window
while (tail > head && nums[dq[tail - 1]] <= nums[i])
tail--; // smaller or equal, and it leaves first: it can never win
dq[tail++] = i;
if (i >= k - 1)
out.push(nums[dq[head]]); // the front is the window's maximum
}
return out;
}
Each printed 3 3 5 5 6 7, then 12 12 12 8 8 6, then 5 5: the third input has a repeated 5, and popping the older copy still leaves a 5 at the front.
Each index in once, out once
A single step can pop a lot: the 12 above popped two values, and a big value after a long fall pops them all. But no index is pushed twice, and once it's popped, from either end, it never comes back. So over the whole run there are n pushes and at most n pops: at most 2n moves, O(n) in all and O(1) per value on average. The deque never holds more than k indexes, so the extra space is O(k).
We counted on a million random values with k = 1,000: 1,000,000 pushes, 999,003 pops from the back and 991 from the front, 1,999,994 moves against the 2,000,000 allowed. The deque was never longer than 21: on random data, few values survive their followers. The two extremes show where the pops go:
| A million values | Pops from the back | Pops from the front | Longest deque |
|---|---|---|---|
| random | 999,003 | 991 | 21 |
| rising, 1, 2, 3 … | 999,999 | 0 | 1 |
| falling, n, n − 1 … | 0 | 999,000 | 1,000 |
On a rising array every newcomer knocks out the one before it, and the deque holds a single index. On a falling one nobody is ever knocked out, the deque fills to k, and every index leaves from the front when it expires. Either way, each index pays for one push and one pop.
Now you keep the window's max
Below, you are the deque. Each value arrives at the right. Pop the back while it's no bigger than the newcomer, push the new index, pop the front when it slides out, then read the maximum off the front. A wrong move is refused with the comparison that rules it out, and the counters show your pushes and pops against 2n. Type your own array and window, or switch to the minimum and watch every comparison flip.
Why not a heap?
A max-heap also gives the biggest value, and it's a common first idea: push (value, index) pairs, and when the top's index has left the window, pop it and look again. That works, because stale entries are thrown out when they reach the top:
import heapq
def max_sliding_window_heap(nums, k):
heap, out = [], [] # (-value, index): the biggest value on top
for i, x in enumerate(nums):
heapq.heappush(heap, (-x, i))
while heap[0][1] <= i - k: # stale on top: its index has left the window
heapq.heappop(heap)
if i >= k - 1:
out.append(-heap[0][0])
return out
It printed 3 3 5 5 6 7 on the first example above. But it's O(n log n), and a stale entry buried under the top stays until it surfaces, which may be never. On our judge, 200,000 values with k = 1,000:
| Input | Heap | Deque | Most entries, heap | Most entries, deque |
|---|---|---|---|---|
| random | 167 ms | 100 ms | 198,740 | 21 |
| rising | 261 ms | 86 ms | 200,000 | 1 |
| falling | 224 ms | 88 ms | 1,000 | 1,000 |
On a rising array the newest value is always on top, so nothing below it is ever popped: the heap kept all 200,000 entries for a window of 1,000. The deque holds only the values that can still win, which is never more than the window.
The minimum, and both at once
For the window's minimum, flip both comparisons: pop the back while it's greater than or equal to the newcomer, and the deque's values rise from front to back, with the minimum at the front. Everything else, the expiry and the 2n count, stays the same.
Some problems want both. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit asks for the longest window whose maximum and minimum are at most limit apart. The window's size isn't fixed, so it's a variable window (Variable-Size Sliding Window: Longest and Shortest): grow the right edge, and while the window is too wide, move the left edge. Two deques keep the max and the min as it moves, and a front leaves when its index falls behind left:
Two deques, one window — A falling deque keeps the maximum and a rising one the minimum; the left edge moves when they're too far apart.
int longestSubarray(const vector<int>& nums, int limit) {
deque<int> hi, lo; // indexes: hi's values fall (front = max), lo's rise (front = min)
int left = 0, best = 0;
for (int right = 0; right < (int)nums.size(); right++) {
while (!hi.empty() && nums[hi.back()] <= nums[right]) hi.pop_back();
while (!lo.empty() && nums[lo.back()] >= nums[right]) lo.pop_back();
hi.push_back(right);
lo.push_back(right);
while (nums[hi.front()] - nums[lo.front()] > limit) {
left++; // too wide: move the left edge
if (hi.front() < left) hi.pop_front();
if (lo.front() < left) lo.pop_front();
}
best = max(best, right - left + 1);
}
return best;
}
from collections import deque
def longest_subarray(nums, limit):
hi = deque() # indexes, values falling: hi[0] is the window's max
lo = deque() # indexes, values rising: lo[0] is the window's min
left = best = 0
for right, x in enumerate(nums):
while hi and nums[hi[-1]] <= x:
hi.pop()
while lo and nums[lo[-1]] >= x:
lo.pop()
hi.append(right)
lo.append(right)
while nums[hi[0]] - nums[lo[0]] > limit:
left += 1 # too wide: move the left edge
if hi[0] < left:
hi.popleft()
if lo[0] < left:
lo.popleft()
best = max(best, right - left + 1)
return best
static int longestSubarray(int[] nums, int limit) {
Deque<Integer> hi = new ArrayDeque<>(); // indexes, values falling: the front is the max
Deque<Integer> lo = new ArrayDeque<>(); // indexes, values rising: the front is the min
int left = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
while (!hi.isEmpty() && nums[hi.peekLast()] <= nums[right]) hi.pollLast();
while (!lo.isEmpty() && nums[lo.peekLast()] >= nums[right]) lo.pollLast();
hi.offerLast(right);
lo.offerLast(right);
while (nums[hi.peekFirst()] - nums[lo.peekFirst()] > limit) {
left++; // too wide: move the left edge
if (hi.peekFirst() < left) hi.pollFirst();
if (lo.peekFirst() < left) lo.pollFirst();
}
best = Math.max(best, right - left + 1);
}
return best;
}
function longestSubarray(nums, limit) {
const hi = new Int32Array(nums.length); // indexes, values falling: hi[hh] is the max
const lo = new Int32Array(nums.length); // indexes, values rising: lo[lh] is the min
let hh = 0, ht = 0, lh = 0, lt = 0;
let left = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
while (ht > hh && nums[hi[ht - 1]] <= nums[right]) ht--;
while (lt > lh && nums[lo[lt - 1]] >= nums[right]) lt--;
hi[ht++] = right;
lo[lt++] = right;
while (nums[hi[hh]] - nums[lo[lh]] > limit) {
left++; // too wide: move the left edge
if (hi[hh] < left) hh++;
if (lo[lh] < left) lh++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
Each printed 2 4 3, the three examples of the problem. The left edge only moves forward, and each index enters and leaves each deque once, so it's still O(n).
The best of the last k answers
The deque doesn't care what the values are. In Jump Game VI you start at index 0, jump at most k steps forward each time, and collect the values you land on; the goal is the biggest total at the last index. Let dp[i] be the best total of a path that ends on i. The path's last jump came from one of the k indexes before it, so
dp[i] = nums[i] + max(dp[i - k], …, dp[i - 1])
That max is a sliding window maximum over the dp values themselves. Written plainly it rescans k answers per index, O(n·k); with a deque of indexes whose dp values fall, it's O(n). One detail moves: the window for dp[i] is i − k up to i − 1, so index i − k is still allowed, and the front leaves only when it's < i - k, one step later than in the window maximum:
int maxResult(const vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n); // dp[i]: the best score of a path that ends on i
deque<int> dq; // indexes, their dp values falling: the front is the best
for (int i = 0; i < n; i++) {
if (!dq.empty() && dq.front() < i - k)
dq.pop_front(); // more than k back: too far to jump from
dp[i] = nums[i] + (dq.empty() ? 0 : dp[dq.front()]);
while (!dq.empty() && dp[dq.back()] <= dp[i])
dq.pop_back();
dq.push_back(i);
}
return dp[n - 1];
}
from collections import deque
def max_result(nums, k):
dp = [0] * len(nums) # dp[i]: the best score of a path that ends on i
dq = deque() # indexes, their dp values falling: dq[0] is the best
for i, x in enumerate(nums):
if dq and dq[0] < i - k:
dq.popleft() # more than k back: too far to jump from
dp[i] = x + (dp[dq[0]] if dq else 0)
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[-1]
static int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n]; // dp[i]: the best score of a path that ends on i
Deque<Integer> dq = new ArrayDeque<>(); // indexes, their dp values falling: the front is the best
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() < i - k)
dq.pollFirst(); // more than k back: too far to jump from
dp[i] = nums[i] + (dq.isEmpty() ? 0 : dp[dq.peekFirst()]);
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i])
dq.pollLast();
dq.offerLast(i);
}
return dp[n - 1];
}
function maxResult(nums, k) {
const n = nums.length;
const dp = new Array(n).fill(0); // dp[i]: the best score of a path that ends on i
const dq = new Int32Array(n); // indexes, their dp values falling: dq[head] is the best
let head = 0, tail = 0;
for (let i = 0; i < n; i++) {
if (tail > head && dq[head] < i - k)
head++; // more than k back: too far to jump from
dp[i] = nums[i] + (tail > head ? dp[dq[head]] : 0);
while (tail > head && dp[dq[tail - 1]] <= dp[i])
tail--;
dq[tail++] = i;
}
return dp[n - 1];
}
Each printed 7 17 0, the problem's three examples. Constrained Subsequence Sum is the same recurrence with one change: a subsequence may also start fresh, so an earlier best that's negative is replaced by 0, and the answer is the best dp anywhere:
from collections import deque
def constrained_subset_sum(nums, k):
dp = [0] * len(nums) # dp[i]: the best sum of a subsequence that ends on i
dq = deque() # indexes, their dp values falling: dq[0] is the best
for i, x in enumerate(nums):
if dq and dq[0] < i - k:
dq.popleft()
dp[i] = x + max(0, dp[dq[0]] if dq else 0) # start afresh when every earlier sum is negative
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return max(dp)
It returned 37, −1 and 23 on the problem's three examples. The Dynamic Programming section comes back to this recurrence: whenever a dp value takes the best of the last k, a deque makes it O(n).
When negative numbers break the window
Shortest Subarray with Sum at Least K looks like a two-pointer window: grow the right edge, and while the sum is at least K, record the length and shrink from the left. That's right when every value is positive (it's Minimum Size Subarray Sum). With negative values it isn't, because dropping a value from the left can raise the sum:
def shortest_by_window(nums, k): # a sliding window: right only when no value is negative
left = total = 0
best = len(nums) + 1
for right, x in enumerate(nums):
total += x
while total >= k:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return best if best <= len(nums) else -1
On 84, −37, 32, 40, 95 with K = 167 it answered 5. The right answer is 3: 32 + 40 + 95. The window started at 84, and once 84 left, the sum fell short, so the window stopped shrinking and never dropped the −37 that came next. On 3,000 random arrays with negatives it was wrong 370 times.
Prefix sums fix it (Introduction to Prefix Sums): with P[j] the sum of the first j values, a subarray from start i to end j sums to P[j] - P[i]. For each end j we want the latest start i with P[i] <= P[j] - K, and a deque of starts handles both sides:
- From the front: while
P[j]minus the front's sum reaches K, record the length and pop the front. Any later end from that start would only be longer, so it's done. - From the back: while
P[j]is no higher than the back's sum, pop the back. Start j is later and no higher, so it beats that start for every end to come.
The starts left in the deque have rising sums, a monotonic deque again:
Prefix sums and the best start — Starts leave from the front once they're used and from the back once a later, lower start beats them.
int shortestSubarray(const vector<int>& nums, int k) {
int n = nums.size();
vector<long long> prefix(n + 1, 0); // prefix[j]: the sum of the first j values
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
deque<int> dq; // start indexes, their prefix sums rising
int best = n + 1;
for (int j = 0; j <= n; j++) {
while (!dq.empty() && prefix[j] - prefix[dq.front()] >= k) {
best = min(best, j - dq.front()); // the shortest from this start: later ends are longer
dq.pop_front();
}
while (!dq.empty() && prefix[j] <= prefix[dq.back()])
dq.pop_back(); // j is later and no higher: a better start for every end
dq.push_back(j);
}
return best <= n ? best : -1;
}
from collections import deque
def shortest_subarray(nums, k):
prefix = [0] # prefix[j]: the sum of the first j values
for x in nums:
prefix.append(prefix[-1] + x)
dq = deque() # start indexes, their prefix sums rising
best = len(nums) + 1
for j, p in enumerate(prefix):
while dq and p - prefix[dq[0]] >= k:
best = min(best, j - dq.popleft()) # the shortest from this start: later ends are longer
while dq and p <= prefix[dq[-1]]:
dq.pop() # j is later and no higher: a better start for every end
dq.append(j)
return best if best <= len(nums) else -1
static int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] prefix = new long[n + 1]; // prefix[j]: the sum of the first j values
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
Deque<Integer> dq = new ArrayDeque<>(); // start indexes, their prefix sums rising
int best = n + 1;
for (int j = 0; j <= n; j++) {
while (!dq.isEmpty() && prefix[j] - prefix[dq.peekFirst()] >= k)
best = Math.min(best, j - dq.pollFirst()); // the shortest from this start: later ends are longer
while (!dq.isEmpty() && prefix[j] <= prefix[dq.peekLast()])
dq.pollLast(); // j is later and no higher: a better start for every end
dq.offerLast(j);
}
return best <= n ? best : -1;
}
function shortestSubarray(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0); // prefix[j]: the sum of the first j values
for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
const dq = new Int32Array(n + 1); // start indexes, their prefix sums rising: dq[head .. tail - 1]
let head = 0, tail = 0, best = n + 1;
for (let j = 0; j <= n; j++) {
while (tail > head && prefix[j] - prefix[dq[head]] >= k)
best = Math.min(best, j - dq[head++]); // the shortest from this start: later ends are longer
while (tail > head && prefix[j] <= prefix[dq[tail - 1]])
tail--; // j is later and no higher: a better start for every end
dq[tail++] = j;
}
return best <= n ? best : -1;
}
Each printed 1 -1 3 3: the problem's three examples, then the array that fooled the two pointers. Each prefix index enters the deque once and leaves at most once: O(n).
Spotting it, and when it breaks
The clues. "The maximum (or minimum) of every window of size k." "The longest window whose max and min are within a limit." A dp value that takes the best of the last k earlier ones. "Shortest subarray with sum at least K" when values can be negative. Whenever the best of a sliding range is needed at every step, keep a deque of the candidates.
The near-misses. A window's sum or count needs no deque, only the plain window (Introduction to Sliding Window). The next greater element for each value is a monotonic stack: nothing ever expires, so one end is enough (Monotonic Stack: Next Greater and Smaller Elements). The k-th largest or the median of a window isn't a deque problem: it needs heaps or a sorted structure, in Heaps & Priority Queues.
When it breaks. The deque needs both window edges to move forward only. Queries on arbitrary ranges, in any order, need a sparse table or a segment tree. And for "at least K" with negatives, the window itself is the wrong tool, as the last section showed.
Bugs that cost a submission
Values instead of indexes. This deque keeps the values and drops the front when the value leaving the window equals it:
from collections import deque
def max_sliding_window(nums, k):
dq, out = deque(), [] # values this time, not indexes
for i, x in enumerate(nums):
if i >= k and dq[0] == nums[i - k]:
dq.popleft() # the value leaving matches the front, so drop the front
while dq and dq[-1] <= x:
dq.pop()
dq.append(x)
if i >= k - 1:
out.append(dq[0])
return out
On 5, 5, 1 with k = 2 it returned [5, 1]; the right answer is [5, 5]. Popping on equal values threw away the older 5, and when the older 5 left the window, the check matched the newer one and dropped it too. Store indexes, and the front leaves exactly when its index does.
The front expires one step late. The window ending at i starts at i − k + 1, so index i − k is already out:
from collections import deque
def max_sliding_window(nums, k):
dq, out = deque(), []
for i, x in enumerate(nums):
if dq and dq[0] < i - k: # < where it should be <=
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(nums[dq[0]])
return out
On 9, 1, 2, 3 with k = 2 it returned [9, 9, 3], against [9, 2, 3]: the 9 stayed one window too long. Write dq[0] <= i - k.
The same test borrowed for Jump Game VI. There the window for dp[i] is i − k up to i − 1, so <= drops a jump that's allowed. On 1, −1, −2, 4, −7 and 3 with k = 2 it returned −2 instead of 7: the best path needs a jump of exactly 2. Before writing the expiry, say which indexes the window holds.
if where it should be while. In Shortest Subarray, one end can finish several starts at once:
from collections import deque
def shortest_subarray(nums, k):
prefix = [0] # prefix[j]: the sum of the first j values
for x in nums:
prefix.append(prefix[-1] + x)
dq = deque() # start indexes, their prefix sums rising
best = len(nums) + 1
for j, p in enumerate(prefix):
if dq and p - prefix[dq[0]] >= k: # if where it should be while
best = min(best, j - dq.popleft()) # the shortest from this start: later ends are longer
while dq and p <= prefix[dq[-1]]:
dq.pop() # j is later and no higher: a better start for every end
dq.append(j)
return best if best <= len(nums) else -1
On 84, −37, 32, 40, 95 with K = 167 it returned 5 instead of 3: at the last end it popped start 0 and stopped, never trying start 2.
A list's pop(0) as the front. In Python, list.pop(0) moves everything behind it (Introduction to Queues), and the deque can hold k items. Use collections.deque.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
dp[i] takes the best of dp[i - k] to dp[i - 1]. When should the front leave?Multiple choice
Multiple choice
Practice problems
In the order this lesson builds up to them:
- Sliding Window Maximum: the deque itself.
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit: two deques on a variable window.
- Jump Game VI: the best of the last k
dpvalues. - Constrained Subsequence Sum: the same, with a fresh start allowed.
- Shortest Subarray with Sum at Least K: prefix sums and a deque of starts.
That's the last lesson on queues. Next, Data Structure Design: whole classes, such as an LRU cache, built by joining a hash map to a list.