LeetCode 239 ·
Hard
Sliding Window Maximum
Return the maximum of each contiguous window of size k.
Try it
Step through the core mechanic. The simulator below runs the stack / monotonic stack shape this problem is built on.
Interactive · Monotonic deque · sliding window max deque holds indices, values strictly decreasing front→back
array
0
4
1
1
2
7
3
3
4
5
5
9
6
2
7
6
8
8
deque (front → back)
i=0 4
r=0, value=4 · push idx 0
emitted maxes
(none yet — window not full)
Why O(n).
Each index is pushed exactly once and popped at most once — 2n operations
total across the whole walk. Inside the inner pop-back loop you might pop
several elements at once, but the amortised work per outer step is
O(1). The front of the deque is always the index of the current window's
maximum, so reading it is O(1).
The approach
A deque of indices kept strictly decreasing by value. Pop the front when it falls out of the window; pop the back while the incoming value dominates. The front is always the window max.
| Aspect | Value |
|---|---|
| Pattern | Stack / monotonic stack |
| Recognise it by | Max of every length-k window in O(n). |
| Time complexity | O(n) |
| Space complexity | O(k) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.