1Understand
The idea
For the maximum of every sliding window, keep a deque of indices whose values decrease from front to back. Drop the front when it leaves the window, and drop from the back every value smaller than the newcomer, since it can never be a maximum again. The front is always the current maximum, giving O(n) overall.
Intuition
For the maximum of every sliding window, keep a deque of indices whose values decrease from front to back. The front is always the current maximum.
Drop the front when it leaves the window. From the back, drop every index whose value is ≤ the newcomer, those can never be the max while the newcomer remains. Each index enters and leaves the deque once.
A plain priority queue also works but needs lazy deletion and is slower; the monotonic deque is O(n).
What you will be able to do
- Keep indices in a monotonic deque
- Expire items that leave the window
When to use it
- Maximum / minimum of every window of size k
- Window condition depends on the max or min
2See it
Walkthrough
Sliding window maximum
a = [1, 3, 2, 5], k = 3, monotonic decreasing deque of indices.
1 / 4
Push 0. Deque indices with decreasing values: front is the max.
Live template
Line 4 active
Complexity: time O(n), space O(k)
Time O(n), space O(k). Recomputing max per window is O(n·k). A heap solution is O(n log n) with stale entries. Use this whenever you need min or max over a moving fixed window.
Read the walkthrough as text
Sliding window maximum. nums = [1,3,-1,-3,5,3,6,7], k = 3.
- First window
[1,3,-1]: deque indices of decreasing values → front3. Max3. - Slide: drop indices
< i-k+1; push new value after clearing smaller backs. - Windows' maxima:
3, 3, 5, 5, 6, 7.
In code:
from collections import dequedq = deque() # indices, nums[dq] decreasingfor i, x in enumerate(nums):while dq and dq[0] <= i - k: dq.popleft()while dq and nums[dq[-1]] <= x: dq.pop()dq.append(i)if i >= k - 1: out.append(nums[dq[0]])
3Recognise it
Kinds of problems (4)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Sliding window maximum
Example. Max in every window of size k.
How. Deque of indices with decreasing values; drop left when index leaves window; front is max.
Sliding window minimum
Example. Min in every window of size k.
How. Same structure with increasing order (pop while back >= new value).
Longest subarray with max − min ≤ limit
Example. Longest subarray where max−min ≤ limit.
How. Two deques (or one each) track window max and min while you slide right/left.
Shortest subarray with sum ≥ k (with prefix sums)
Example. Shortest positive subarray sum at least k.
How. Prefix sums + deque of indices with increasing prefix for O(n) monotone queue.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
list.pop(0)
Why it happens. Window max uses a queue; list.pop(0) is the obvious dequeue.
How it fails. dq as list and dq.pop(0) when expiring the left index, O(k) per window, O(n·k) overall.
Fix. collections.deque with popleft() and append(), both ends O(1).
Expired items kept
Why it happens. You maintain monotonic order but forget the window width.
How it fails. k=3 but deque front index is 0 while i=5, stale max from outside the window pollutes the answer.
Fix. Before using dq[0], while dq[0] <= i - k: popleft().
Wrong comparison
Why it happens. Pop while strictly less and pop while less-or-equal feel interchangeable.
How it fails. Max deque with while a[dq[-1]] < x when duplicates need the older index dropped, wrong max persists.
Fix. Sliding max: pop while <= x so equal values refresh; min deque: pop while >= x.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.