Where it runs
1. The problem
A monitoring panel shows the highest latency over the last 3 samples (measurements) and updates with every new sample. The window slides: a fresh sample comes in on the right, the oldest one leaves on the left, and you report the maximum of what is inside. You have to do that for every position of a long stream.
The simple way is to look through the window again each time: for every position, check all k values and take the biggest. On 1,000,000 samples with a window of 1000 that is about 1,000,000,000 comparisons. Most of them repeat work that was already done for the previous window.
For a sum in a sliding window two actions were enough: add the new value and subtract the one that left. You can't subtract a maximum that way. When the biggest value leaves the window, the next biggest is unknown until you look through the window again. You need a structure that remembers the candidates for the maximum, in order, ahead of time.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmaxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)Find the maximum of every window of 3 numbers. The deque keeps indices whose values could still become a maximum.
Bars: the 40 values. The window is 10 long, a quarter of the array, and the size table keeps that ratio.
One operation is one comparison of two values. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n·k)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- maximum or minimum of every window of size k
- sliding window maximum/minimum
- shortest subarray with a sum at least K
- need both ends of a queue popped/pushed
- deque, double-ended queue
Looks similar, isn't
- Monotonic stack
A stack only ever drops from the top. A deque also drops the front when a value leaves the window.
- Sliding window (fixed size)
A rolling sum survives a subtraction. A maximum does not, which is why this exists.
- Binary heap / priority queue
A heap gives the maximum in log n. It cannot delete the element that just left the window.
- Stack (LIFO)
A plain stack keeps no order and has one open end. Both limits break this problem.
n up to 1e6 gives O(n), since each index enters and leaves once. Memory is O(k) for the window.
On LeetCode
Problems that need the maximum or minimum of a sliding window at every step. A deque of positions with falling values keeps the answer at the front and costs O(n) in total.
The lesson task exactly, a fixed window of k and its maximum at every step.
Build the deque itself on a fixed array with a head and a tail index that wrap around.
- 1438.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (opens in a new tab)Medium
A variable window with two deques, one for the maximum and one for the minimum, and shrink while they differ by more than limit.
Run a deque of rising values over the prefix sums, because negative numbers break the plain sliding window.