On this page
Description
The maximum of every window of k consecutive values: rescanning each window is O(n * k). A heap gives O(n log n) but must remove values that leave the window. A deque of candidates does it in O(n) - by keeping only values that could still become the maximum.
This skill covers the monotonic deque: indices whose values decrease from front to back, so the front is always the window's maximum. Smaller values leave from the back and expired indices leave from the front. It also covers pairing two deques to track both extremes of a window that grows and shrinks.
We'll go from simple to more technical:
- The pattern: Sliding Window Maximum with a deque of indices.
- A second flavor: two deques for max and min in a variable window.
- Where rolling extremes show up (dashboards, rate limiters, streaming aggregations).
- What breaks it: no expiry check, storing values, one deque for two extremes, early reads.
The approach
Java
int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing front to back
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // left the window
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // can never be the max again
dq.offerLast(i);
if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
}
return result;
}
Python
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
result = []
dq = deque() # indices, values decreasing front to back
for i, x in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft() # left the window
while dq and nums[dq[-1]] <= x:
dq.pop() # can never be the max again
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
A value that is smaller than a newer one can never be the maximum again: the newer value is larger and stays in the window longer. So the deque's values decrease from front to back, and the front is the maximum. The front must also be dropped once its index leaves the window (index <= i - k), which is why the deque stores indices, not values - on a decreasing array such as 9, 8, 7, ... nothing is ever popped from the back, and without the expiry check the first value would stay the "maximum" forever. Each index enters and leaves once: O(n).
A second flavor: two deques for a variable window
The longest subarray whose max - min is at most limit needs both extremes of a window that grows and shrinks. Keep a decreasing deque for the maximum and an increasing one for the minimum, and move the left edge while the window is too spread out:
Java
int longestSubarray(int[] nums, int limit) {
Deque<Integer> maxQ = new ArrayDeque<>(), minQ = new ArrayDeque<>();
int left = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
while (!maxQ.isEmpty() && nums[maxQ.peekLast()] <= nums[right]) maxQ.pollLast();
while (!minQ.isEmpty() && nums[minQ.peekLast()] >= nums[right]) minQ.pollLast();
maxQ.offerLast(right);
minQ.offerLast(right);
while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > limit) {
left++;
if (maxQ.peekFirst() < left) maxQ.pollFirst();
if (minQ.peekFirst() < left) minQ.pollFirst();
}
best = Math.max(best, right - left + 1);
}
return best;
}
Python
from collections import deque
def longest_subarray(nums: list[int], limit: int) -> int:
max_q, min_q = deque(), deque()
left = best = 0
for right, x in enumerate(nums):
while max_q and nums[max_q[-1]] <= x:
max_q.pop()
while min_q and nums[min_q[-1]] >= x:
min_q.pop()
max_q.append(right)
min_q.append(right)
while nums[max_q[0]] - nums[min_q[0]] > limit:
left += 1
if max_q[0] < left:
max_q.popleft()
if min_q[0] < left:
min_q.popleft()
best = max(best, right - left + 1)
return best
Comparing each new value only with the window's first value misses extremes in the middle: on [1, 5, 6, 7, 8, 10, 6, 5, 6] with limit 4 it answers 7 instead of 5.
Where you'll see it
Monitoring dashboards show "maximum CPU over the last 5 minutes" updated every second; rate limiters and trading systems track rolling highs and lows; streaming engines implement sliding-window max/min aggregations with exactly this deque, in O(1) amortized per event.
Which tool for which job?
| You need | Use |
|---|---|
| Max or min of every fixed window | a monotonic deque of indices |
| Max - min within a limit, longest window | two deques and a moving left edge |
| A DP over the best of the last k states | a monotonic deque over dp values |
| Shortest subarray with sum >= K, negatives allowed | a deque over prefix sums |
| GCD, product or any associative op over a window | a two-stack queue with running aggregates |
| Any order statistic of the window | a sorted map of counts |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No expiry check | 9 8 7 6 5 4 with k = 3 gives 9, 9, 9, 9 | drop the front once its index is <= i - k |
| Storing values, not indices | expiry can't be checked | store indices |
| One deque for max - min | middle extremes are missed | a max deque and a min deque |
| Reading before the first full window | partial windows in the output | start at i = k - 1 |
| A lazy max-heap instead | it held all 100,000 entries on increasing input | the deque holds at most k |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why can a value be dropped from the back when a larger value arrives?
Show answer
The newer value is larger and will stay in the window at least as long, so the older, smaller value can never be the maximum of any future window.
2. Why does the deque store indices rather than values?
Show answer
To know when the front has left the window (index <= i - k). On a decreasing array nothing is ever popped from the back, so the expiry check is the only thing that removes old maxima.
3. What does the longest subarray with max - min <= limit need that sliding window maximum doesn't?
Show answer
Both extremes - a decreasing deque for the maximum and an increasing deque for the minimum - and a variable window: move the left edge (expiring deque fronts) while max - min is too large.
Key takeaways
- Keep indices with decreasing values; drop smaller values from the back, expired indices from the front.
- The front is the window's maximum; O(n) total.
- Store indices so the front can expire.
- Two deques track max and min for a variable window.