Sliding Window Maximum
A value that is older and no larger than the newcomer can never be the maximum of any later window, so throw it away the moment the newcomer arrives. What survives is a deque sorted from the front down, and the front is the answer for free.
Find the maximum of every window of 3 values. The deque holds indices from the window whose values could still be the maximum, front to back, and the front is always the answer.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
Back of the deque is 1, the new value is 3. Pop or push?
Answer: Pop 1. 3 is at least as larger and newer, so 1 is dominated on both counts.
Back of the deque is 3, the new value is -1. Pop or push?
Answer: Push -1. 3 is larger, so it may still be the maximum after -1 joins.
Back of the deque is -1, the new value is -3. Pop or push?
Answer: Push -3. -1 is larger, so it may still be the maximum after -3 joins.
Back of the deque is -3, the new value is 5. Pop or push?
Answer: Pop -3. 5 is at least as larger and newer, so -3 is dominated on both counts.
Back of the deque is -1, the new value is 5. Pop or push?
Answer: Pop -1. 5 is at least as larger and newer, so -1 is dominated on both counts.
Back of the deque is 5, the new value is 3. Pop or push?
Answer: Push 3. 5 is larger, so it may still be the maximum after 3 joins.
Back of the deque is 3, the new value is 6. Pop or push?
Answer: Pop 3. 6 is at least as larger and newer, so 3 is dominated on both counts.
Back of the deque is 5, the new value is 6. Pop or push?
Answer: Pop 5. 6 is at least as larger and newer, so 5 is dominated on both counts.
Back of the deque is 6, the new value is 7. Pop or push?
Answer: Pop 6. 7 is at least as larger and newer, so 6 is dominated on both counts.
How it runs, step by step
Find the maximum of every window of 3 values. The deque holds indices from the window whose values could still be the maximum, front to back, and the front is always the answer.
Finding the maximum of every window of 3 values with a deque that keeps the maximum at its front.
The deque is empty, so 1 goes in and is the front.
The deque is empty. 1 is pushed and becomes the front.
3 enters. The back of the deque is 1, which is not larger than 3 and will leave the window sooner. It can never be the maximum again, so pop it.
3 enters and 1 at the back is dominated, so it is popped.
The deque is empty, so 3 goes in and is the front.
The deque is empty. 3 is pushed and becomes the front.
-1 enters. The back of the deque is 3, which is larger than -1, so it stays. Push -1 behind it.
-1 enters. 3 at the back stays and -1 is pushed behind it.
Window 0 to 2 is complete. Its maximum is the front of the deque, 3, read in O(1).
The maximum of window 0 to 2 is 3, the front of the deque.
-3 enters. The back of the deque is -1, which is larger than -3, so it stays. Push -3 behind it.
-3 enters. -1 at the back stays and -3 is pushed behind it.
Window 1 to 3 is complete. Its maximum is the front of the deque, 3, read in O(1).
The maximum of window 1 to 3 is 3, the front of the deque.
The window slides to indices 2 to 4. 3 at index 1 was the front but has left the window, so drop it.
The window moves to indices 2 to 4. 3 has left the window and is removed from the front of the deque.
5 enters. The back of the deque is -3, which is not larger than 5 and will leave the window sooner. It can never be the maximum again, so pop it.
5 enters and -3 at the back is dominated, so it is popped.
5 enters. The back of the deque is -1, which is not larger than 5 and will leave the window sooner. It can never be the maximum again, so pop it.
5 enters and -1 at the back is dominated, so it is popped.
The deque is empty, so 5 goes in and is the front.
The deque is empty. 5 is pushed and becomes the front.
Window 2 to 4 is complete. Its maximum is the front of the deque, 5, read in O(1).
The maximum of window 2 to 4 is 5, the front of the deque.
3 enters. The back of the deque is 5, which is larger than 3, so it stays. Push 3 behind it.
3 enters. 5 at the back stays and 3 is pushed behind it.
Window 3 to 5 is complete. Its maximum is the front of the deque, 5, read in O(1).
The maximum of window 3 to 5 is 5, the front of the deque.
6 enters. The back of the deque is 3, which is not larger than 6 and will leave the window sooner. It can never be the maximum again, so pop it.
6 enters and 3 at the back is dominated, so it is popped.
6 enters. The back of the deque is 5, which is not larger than 6 and will leave the window sooner. It can never be the maximum again, so pop it.
6 enters and 5 at the back is dominated, so it is popped.
The deque is empty, so 6 goes in and is the front.
The deque is empty. 6 is pushed and becomes the front.
Window 4 to 6 is complete. Its maximum is the front of the deque, 6, read in O(1).
The maximum of window 4 to 6 is 6, the front of the deque.
7 enters. The back of the deque is 6, which is not larger than 7 and will leave the window sooner. It can never be the maximum again, so pop it.
7 enters and 6 at the back is dominated, so it is popped.
The deque is empty, so 7 goes in and is the front.
The deque is empty. 7 is pushed and becomes the front.
Window 5 to 7 is complete. Its maximum is the front of the deque, 7, read in O(1).
The maximum of window 5 to 7 is 7, the front of the deque.
Answer [3, 3, 5, 5, 6, 7]. Every value was pushed once and popped at most once, 8 pushes and 7 pops for 8 values, so the whole scan is O(n) with a deque of at most 3.
The maximum of each window is [3, 3, 5, 5, 6, 7]. 8 pushes and 7 pops in all.
Remember
- The deque stores indices, not values, so it can tell when the front has left the window.
- Pop from the back while the back is no larger than the newcomer: older and smaller is dominated.
- Each value enters once and leaves once, so n slides cost O(n) in total.
Topics covered
Where this is used
Data analysisRolling maximum in pandas
Series.rolling(k).max() is this algorithm behind an API. Recomputing each window from scratch is O(n * k), which on a million rows with a 500-wide window is half a billion comparisons, so pandas walks the series once and keeps a deque of indices that are still candidates. The window width stops mattering to the runtime, which is why widening the window does not slow the call down.
NetworkingBBR congestion control
BBR estimates the bottleneck bandwidth as the largest delivery rate seen in roughly the last ten round trips and the propagation delay as the smallest RTT seen in roughly the last ten seconds, both windowed extremes over a stream that never ends. Linux tracks the bandwidth maximum in lib/win_minmax.c using the same domination rule as here: a new maximum makes every older sample worthless, so the older ones are discarded on the spot. It keeps the best three samples rather than a full deque, trading a little accuracy for constant space per connection. The min RTT is cheaper still, since tcp_bbr.c holds one value and its timestamp and resets it when the ten second window runs out.
GraphicsGrayscale dilation and erosion
Dilating an image with a flat k by k structuring element is the maximum over a k-wide window, run once across every row and once down every column, and erosion is the same with the minimum. The naive form costs O(k) per pixel, which is why big structuring elements used to be avoided; the deque makes the cost per pixel independent of k. SciPy exposes the one-dimensional case directly as ndimage.maximum_filter1d.
FinanceDonchian channels in backtests
A Donchian channel is defined as the highest high and lowest low of the last N bars, so plotting one is literally a sliding window maximum and minimum. A backtest replays millions of bars and re-runs the whole sweep for every candidate N, so the O(n * N) rescan is what makes a parameter sweep slow. The deque gives constant amortized work per bar, and it also fits a live feed, where each new tick must be handled before the next one arrives.
Why it works this way
Why the deque holds indices instead of the values
Duplicate values are what break the value-only version. If the deque held values you could not tell whether the 7 at the front is the one that just expired or a later 7 still inside the window, so you would drop a maximum that is still valid. With indices there is no ambiguity: expiry is one comparison against i - k, and a[front] still hands you the value whenever you need it.
A while loop inside a for loop, and still O(n)
Count pushes, not loop iterations. A single step can pop k - 1 entries, but only because k - 1 earlier steps each paid to push one, so the back-pops across the whole run add up to at most n no matter how they clump. The worst case for one step really is O(k); only the average over the run is constant. That matters if you need a hard per-step deadline rather than a total, because this algorithm does not give you one.
Why not just keep a max-heap of the window?
A heap hands you the largest thing it holds, but it cannot remove the element that just left the window: it only removes the top. The usual fix is lazy deletion, popping expired tops until the root is inside the window, but then the heap grows to hold every element seen so far, so a push costs O(log n) and the run costs O(n log n). The deque sidesteps it because a dominated element can be deleted the moment it is dominated, so nothing that is not a possible future answer is ever stored.
When the back ties with the newcomer, <= or <?
Popping on <= throws away the older of two equal values. That is safe for the maximum, because equal values give the same answer and the newer one survives in the window longer, so the older one can never be needed. Popping on < keeps both, which is also correct and only makes the deque longer. The difference shows up when you want the index of the maximum rather than its value: <= leaves the latest of the tied indices at the front, < leaves the earliest.
Read more
- Minimum Stack / Minimum Queuecp-algorithms
- Double-ended queueWikipedia
- Streaming Maximum-Minimum Filter Using No More than Three Comparisons per ElementLemire, arXiv · arxiv.org
- lib/win_minmax.c, the windowed min/max tracker used by BBRLinux kernel · github.com
- Sliding WindowUSACO Guide