AdvancedSliding Window
Sliding window maximum with a deque
Keep a deque of indices whose values decrease. The front is always the window's max; pop smaller values from the back as you go.
The idea
Recomputing the max of each window is O(k) per window. Instead, keep indices in a deque with decreasing values. A new value removes everything smaller from the back (they can never be the max again), and the front drops off when it leaves the window.
The front of the deque is the current window's maximum.
Worked example
[1, 3, -1, -3, 5, 3, 6, 7], k = 3
- 1, then 3 removes 1 → [3]; -1 → [3, -1] → max 3
- -3 → [3, -1, -3] → max 3; 5 removes all → [5] → max 5
- maxes: 3, 3, 5, 5, 6, 7
In code (Python)
from collections import deque
def max_sliding_window(nums, k):
window, maxes = deque(), [] # indices, values decreasing
for i, x in enumerate(nums):
while window and nums[window[-1]] < x:
window.pop()
window.append(i)
if window[0] <= i - k:
window.popleft() # left the window
if i >= k - 1:
maxes.append(nums[window[0]])
return maxesO(n) time, O(k) space.
How to spot it
- Max or min of every window, or of a range that keeps moving.
Common mistakes
- Storing values instead of indices, so you can't tell when the front left the window.
- Appending results before the first full window.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →