The problem
Given a list of numbers and a window size k, slide the window from left to right one step at a time and report the largest number in each window.
Input: [1, 3, 1, 2, 1, 5, 3, 6, 7], k = 3 Output: [3, 3, 2, 5, 5, 6, 7]
Picture it
Picture riding a train and seeing k towers through the window at once. You keep a short list of candidates, tallest first. When a new tower appears, any shorter towers in the list are now useless (the new one is taller and will stay in view longer), so they are thrown out. The front of the list is always the tallest in view; if it has slid out of the window, drop it.
How to recognise it
- A window of fixed size k slides one step at a time, and you need the maximum (or minimum) of each window.
- A plain running maximum fails, because the maximum can leave the window, and then you need the next-best value at once.
- Smaller values that arrive before a bigger one can never be the maximum again while that bigger one is in the window. That is the hint for a structure that throws them away.
- n is up to 10^5 and k can be as large as n, so recomputing each window is too slow.
Start with brute force
Take the maximum of every window directly.
def max_window_brute(h, k):
return [max(h[i:i + k]) for i in range(len(h) - k + 1)]
There are n − k + 1 windows, each costing O(k), so time is O(n · k). The worst case is k around n/2: with n = 10^5 that is about 2.5 × 10^9 steps. Space is O(k) for each slice.
From brute force to the idea
- Find the waste. Neighbouring windows share k − 1 values, but each maximum is recomputed from scratch.
- Drop values that can never win. When x arrives, any earlier value that is no bigger than x is useless: x is at least as big and will stay in the window longer. Pop those from the back.
- Keep a decreasing queue. After the pops, the values in the deque are in decreasing order from front to back, so the front is the maximum of the window.
- Store positions, not values. The deque holds indices, so you can tell when the front has slid out: if
dq[0] <= i - k, it is no longer in the window, so pop it from the front. Only the front can be out of date, because the deque is in order of position. - Report once the window is full. From
i = k - 1onwards, appendh[dq[0]].
This is the key idea: a deque of positions with decreasing values, where the front is always the current maximum.
The key idea
A deque kept in decreasing order: the front is always the maximum. Each tower is added and removed at most once: O(n).
Python solution
def max_window(h, k):
dq, out = deque(), [] # positions, tallest at front
for i, x in enumerate(h):
while dq and h[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(h[dq[0]])
return outLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · k): every window is scanned | O(k): one slice at a time, besides the output |
| Monotonic deque (shown code) | O(n): each index is pushed once and popped at most once | O(k): the deque holds at most k positions, besides the output |
The inner while can pop many items on one step, but there are only n pushes, so all pops together total at most n.
Edge cases
- k = 1 (
[4, 2]): returns the list itself,[4, 2]. - k equals the length (
[4, 2, 5], k = 3): returns one maximum,[5]. - Falling values (
[5, 4, 3, 2, 1], k = 3): nothing is popped from the back, the deque grows to k, and old fronts expire:[5, 4, 3]. - Equal values (
[2, 2, 2], k = 2): returns[2, 2]. Because of<=, the older copy is popped, so the deque keeps the newest one, which stays in the window longest. - Empty list, or k larger than the list: returns
[]; no window is ever full. - Missing import: the code needs
from collections import deque; without it the call raisesNameError.
Common mistakes
- Storing values instead of positions, so you cannot tell when the front has left the window.
- Expiring with
dq[0] < i - k, one step late. The window is then k + 1 wide:[3, 1, 1, 1]with k = 2 returns[3, 3, 1]instead of[3, 1, 1]. - Using a max-heap without removing expired entries, which reports a value that has already left the window.
- Worrying about
<versus<=in the back pops. Both give correct answers;<=just keeps the deque smaller when values repeat.
For each window of size k, report the maximum minus the minimum. For [1, 3, 1, 2, 1, 5, 3, 6, 7] with k = 3 the answer is [2, 2, 1, 4, 4, 3, 4]. Describe your approach, then write it if you like.
Compare with our answer
Run two deques side by side: one decreasing (front is the maximum), and one increasing (front is the minimum), which pops from the back while the back is at least the new value. Expire both fronts in the same way.
from collections import deque
def window_range(h, k):
hi, lo, out = deque(), deque(), []
for i, x in enumerate(h):
while hi and h[hi[-1]] <= x:
hi.pop()
while lo and h[lo[-1]] >= x:
lo.pop()
hi.append(i)
lo.append(i)
if hi[0] <= i - k:
hi.popleft()
if lo[0] <= i - k:
lo.popleft()
if i >= k - 1:
out.append(h[hi[0]] - h[lo[0]])
return out
Time O(n), space O(k).
A strong answer mentions: a second deque with the comparison flipped, expiring both fronts, and why it is still O(n).
1. For each day you must report the lowest price over the last 30 days. Which approach fits best?
The minimum version uses an increasing deque: the front is the cheapest day still in range, and expired days leave from the front. A heap keeps prices that have left the range on top unless they are removed, and a reset loses days that are still in the window.
2. Why is the shown code O(n) even though a while loop sits inside the for loop?
All the pops across the whole run are bounded by the n pushes. One step can pop many positions, and the deque can grow to k on falling input; fast pops alone would not be enough without that bound.
3. A learner writes if dq[0] < i - k: to expire the front. Which call now returns a wrong answer?
The 3 should leave when i = 2, but is kept one step too long, so the result is [3, 3, 1]. In the rising list the front is popped from the back anyway, with equal values the stale front has the right value, and with k equal to the length only one window is ever reported.
Score 60% or more and the lesson is marked complete.