Appearance
4.6.6 — Sliding Window Maximum
LeetCode 239 · Hard
The problem
A window of size k slides along the array one step at a time. Return the maximum inside the window at every position.
nums = [1,3,-1,-3,5,3,6,7], k = 3
windows: [1 3 -1] -3 5 3 6 7 → 3
1 [3 -1 -3] 5 3 6 7 → 3
1 3 [-1 -3 5] 3 6 7 → 5
...
answer: [3, 3, 5, 5, 6, 7]Up to 100,000 elements.
The pattern
Recomputing the maximum from scratch for each window is O(n \cdot k) — too slow.
A heap gets you to O(n \log k): push each element, and when the top of the heap has fallen out of the window, discard it. Perfectly acceptable, and worth mentioning.
But there is an O(n) answer, and it comes from one observation:
If a smaller value sits before a larger value in the window, the smaller one can never be the maximum again. The larger one is in every future window that still contains the smaller one, and it outlives it.
So that smaller value is useless forever. Throw it away. What is left is a list of values in decreasing order, and the front of it is the current maximum.
The structure holding them is a monotonic deque — a double-ended queue whose contents always decrease from front to back. You push and pop at the back to keep the order, and pop from the front when the maximum falls out of the window.
Store indices, not values, so you can tell when something has slid out of range.
The solution
python
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque() # indices, values decreasing
result = []
for i in range(len(nums)):
# 1. drop indices that have slid out of the window
if dq and dq[0] <= i - k:
dq.popleft()
# 2. drop smaller values from the back — they can never win
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
# 3. this index is now a candidate
dq.append(i)
# 4. once the first full window exists, the front is its maximum
if i >= k - 1:
result.append(nums[dq[0]])
return resultts
function maxSlidingWindow(nums: number[], k: number): number[] {
const dq: number[] = []; // indices, values decreasing
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
if (dq.length && dq[0] <= i - k) dq.shift();
while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}Step 1 removes at most one index, because only one can leave the window per step. dq[0] <= i - k says the front index is now outside the window that ends at i.
Step 2 uses <, not <=. With <=, equal values would evict each other. That still gives the right maximum, but it discards duplicates that are needed later — keeping equal values is safer and costs nothing.
Step 4 waits for the first full window. With k = 3, the first complete window ends at index 2, which is k - 1.
Use a real deque. In Python, collections.deque pops from either end in O(1). A plain list with pop(0) is O(n) and turns this into a quadratic solution. JavaScript's Array.shift() has the same problem — it is O(n) in principle, though engines optimise small arrays, so for a strict O(n) you would keep a head index and never actually shift. That trap is exactly the array.shift() production bug from 4.7.
Trace
nums = [1,3,-1,-3,5,3,6,7], k = 3
| i | value | deque (values) | output |
|---|---|---|---|
| 0 | 1 | [1] | — |
| 1 | 3 | [3] (1 evicted) | — |
| 2 | −1 | [3, -1] | 3 |
| 3 | −3 | [3, -1, -3] | 3 |
| 4 | 5 | [5] (all evicted) | 5 |
| 5 | 3 | [5, 3] | 5 |
| 6 | 6 | [6] | 6 |
| 7 | 7 | [7] | 7 |
[3, 3, 5, 5, 6, 7] ✓
Complexity
O(n) time. The while inside the for looks quadratic and is not.
Every index is pushed onto the deque exactly once and popped at most once. So across the whole run there are at most n pushes and n pops — 2n operations total, not n per iteration. This is the same amortized argument as 4.4.9 and the monotonic stack in 4.8.
O(k) space — the deque never holds more than one window's worth of indices.
The heap version, for comparison
Push (-value, index) into a min-heap so the largest value sits on top. Before reading the maximum, discard any top entry whose index has left the window.
O(n \log k) time, O(n) space in the worst case, because stale entries linger until they reach the top. It is easier to write and easier to explain, and it is a perfectly good first answer. The deque is the one that meets O(n).
Where this goes next
- Shortest Subarray with Sum at Least K — with negative numbers allowed, the plain window breaks, and the answer combines prefix sums with a monotonic deque.
- Jump Game VI — DP where each state takes the maximum over a window of previous states. The deque makes the transition O(1) instead of O(k), turning O(nk) into O(n).
- Constrained Subsequence Sum — same idea again.
The rule: when a DP transition or a query needs the maximum or minimum over a sliding range, a monotonic deque makes it O(1) per step. That is the reason this problem is worth real effort — it is a building block, not an endpoint.
What the interviewer will push on
"Why is this O(n) when there is a loop inside a loop?" Each index enters and leaves the deque once, so total work is 2n.
"Why store indices instead of values?" Because you need to know when an entry has slid out of the window, and only the index tells you that.
"Why < and not <= in the eviction?" Equal values would evict each other. Keeping them is harmless and safer.
"Could you use a heap?" Yes, O(n \log k) with lazy deletion of stale entries. Say it, then say why the deque beats it.
"What if you needed the window minimum instead?" Flip the comparison. The deque becomes increasing and the front is the minimum. Being able to say this instantly shows you understood the structure rather than the problem.
One thing to volunteer: name the eviction rule as a sentence. "A smaller value that arrived earlier can never be the maximum again, because the larger later value outlives it." Everything in the code follows from that.
Next: 4.7 covers the structures behind this deque, and the stack that the next problem group is built on.