Sliding window maximum in O(n): the monotonic deque, traced and coded
Elman Huseynov · 2026-11-20
Short answer. The sliding window maximum in O(n) uses a monotonic deque. The deque holds indexes whose values decrease from front to back. A new element evicts everything smaller from the back. The front leaves when it falls out of the window. The front is always the maximum of the current window.
What is the sliding window maximum?
Given an array and a number k. A window of length k slides left to right. For each position, report the maximum inside the window.
Naively you scan k elements per window. That is O(n · k). With n and k at a hundred thousand, that is ten billion operations.
The monotonic deque gives O(n). Each element enters the deque once and leaves once.
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)Find the maximum of every window of 3 numbers. The deque keeps indices whose values could still become a maximum.
Bars: the 40 values. The window is 10 long, a quarter of the array, and the size table keeps that ratio.
One operation is one comparison of two values. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n·k)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
The pattern page: when to use it, and a template in six languages
How does the deque find the sliding window maximum?
- The deque holds indexes. Their values decrease from front to back.
- A new element arrives. While the back is smaller, pop the back. It can never be the maximum again.
- Push the new index to the back.
- The front fell outside the window: pop the front.
- Once the window is full, the front is the maximum.
The key thought: an older and smaller element is useless. The new one outlives it in the window and beats it.
What does one run look like?
Array [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Index 0, value 1: deque [0]. Index 1, value 3: 3 beats 1, pop 0, deque [1]. Index 2, value -1: deque [1, 2]. Window full, maximum 3.
Index 3, value -3: deque [1, 2, 3]. Front 1 is inside window 1..3, maximum 3. Index 4, value 5: pop 3, 2, 1, deque [4]. Maximum 5. Then 5, 6, 7. Answer [3, 3, 5, 5, 6, 7].
How do you write the sliding window maximum in Python?
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indexes, values decreasing
out = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # back is smaller, useless now
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # front left the window
if i >= k - 1:
out.append(nums[dq[0]])
return out
def min_sliding_window(nums, k):
dq, out = deque(), []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] >= x: # comparison flipped
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
The minimum needs one flipped comparison. Everything else is identical.
How does the monotonic deque compare with its neighbours?
| Pattern | Gives | Time | Use when |
|---|---|---|---|
| Monotonic deque | Window maximum or minimum | O(n) | A fixed or growing window |
| Monotonic stack | Nearest greater neighbour | O(n) | No window, just a neighbour |
| Heap with lazy deletion | Window maximum | O(n log n) | You also need the second maximum |
| Segment tree | Maximum of any range | O(log n) per query | Arbitrary ranges, array changes |
How do you solve Shortest Subarray with Sum at Least K?
The array has negative numbers. You need the shortest subarray with sum at least k. A plain window breaks on negatives. Compute prefix sums and keep a deque of indexes with increasing prefixes.
For each new prefix, look at the front. The difference is at least k: record the length, pop the front. While the back is at least the new prefix, pop the back. The monotonicity is over prefixes, not values.
How do you solve Constrained Subsequence Sum?
Find the maximum subsequence sum where neighbouring indexes differ by at most k. dp[i] equals nums[i] plus the best dp over the last k positions. That best value is what the deque provides. Time O(n) instead of O(n · k).
When does a problem need this pattern?
- "Maximum of every window of length k."
- "Minimum over the last k elements" inside a DP.
- "Shortest subarray with sum at least k" with negatives.
- "Difference between window max and min at most limit."
What mistakes break the solution?
- Storing values instead of indexes. Then you cannot tell whether an element left the window.
- Popping the back only on strict less-than. Duplicates pile up. The answer is right, but the deque grows.
- Checking the front before pushing the new element. At k = 1 that loses it.
- Using list.pop(0) instead of deque. Each removal is O(n).
How do you explain it in an interview?
Say: I keep a deque of candidates for the maximum, values decreasing. A new element makes every smaller one before it useless. The front leaves when it falls out of the window.
Give O(n): each index enters and leaves once. Then show it on five numbers.
Drill this pattern on the monotonic deque page. The neighbouring pattern lives on the monotonic stack page.
FAQ
Why not a heap?
A heap works in O(n log n), with lazy deletion of stale indexes. The deque is shorter and linear. Use a heap when you need several top values.
What if the window is bounded by a condition, not a length?
Same deque. The left edge moves by the condition. The front pops while its index is below the left edge. That solves the max-minus-min problem.
Can you keep two deques at once?
Yes. One for the maximum, one for the minimum. Both update every step. That gives the window's range in O(n).
Where does this show up in real systems?
Monitoring: peak load over the last minute. Finance: the highest price over the last n days. Signal processing: a max filter over a window.