Sliding Window Maximum
Problem statement
You're given an array of integers, nums, and a window of size k that
slides across it one position at a time, from the very start to the very
end. At each position, you can only see the k numbers currently inside the
window. Return the maximum value inside the window at every position it
stops at, in order.
Think of nums as a stream of readings — CPU load samples taken once a
second, say — and k as a rolling window of the last k seconds. The
output is the rolling maximum: the worst reading in the last k seconds, at
every second.
Examples
Example 1
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: The window starts at [1,3,-1] (max 3), then slides to [3,-1,-3] (max 3), then [-1,-3,5] (max 5), then [-3,5,3] (max 5), then [5,3,6] (max 6), then finally [3,6,7] (max 7) — six window positions in total for an array of length 8 with k=3.
Example 2
Input: nums = [1], k = 1
Output: [1]
Explanation: With k equal to the whole array's length, there's only one window position, and its maximum is the single value itself.
Hints
Approach
Optimal: Monotonic deque
Intuition
The heap approach's real waste is that it keeps every value ever seen, even ones that can never possibly be a future maximum. If a smaller value sits behind a bigger, more recent value, that smaller value is permanently irrelevant — it will always lose to the bigger one for as long as the bigger one is still in range, and once the bigger one also leaves the window, the smaller one has already left too. So don't keep it at all: use a deque of indices, kept in strictly decreasing order of value (front-to-back). Before adding a new index, pop off the back of the deque any indices whose value is less than or equal to the new one — they're now provably useless. Also drop the front of the deque if its index has fallen out of the current window. The front of the deque is then always the current window's maximum, with no need to search or clean up beyond that.
Steps
- Keep a deque of indices,
dq, kept so thatnumsat those indices is strictly decreasing from front to back. - For each index
i: while the deque isn't empty and the value at its back is less than or equal tonums[i], pop it from the back — it can never be a maximum again whilenums[i]is still around. - Push
ionto the back of the deque. - If the index at the front of the deque has fallen out of the window
(it's
<= i - k), pop it from the front. - Once
i >= k - 1(the window is fully filled), the value at the front of the deque is the current window's maximum — append it to the result.
Dry run
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
| i | value | pop from back while ≤ value | dq after push | pop expired front? | window max (once i ≥ 2) |
|---|---|---|---|---|---|
| 0 | 1 | (empty) | [0] | — | — |
| 1 | 3 | pop 0 (nums[0]=1 ≤ 3) | [1] | — | — |
| 2 | -1 | (nums[1]=3 > -1, stop) | [1, 2] | front 1 ≤ 2-3=-1? no | nums[1] = 3 |
| 3 | -3 | (nums[2]=-1 > -3, stop) | [1, 2, 3] | front 1 ≤ 3-3=0? no | nums[1] = 3 |
| 4 | 5 | pop 3, pop 2, pop 1 (all ≤ 5) | [4] | front 4 ≤ 4-3=1? no | nums[4] = 5 |
| 5 | 3 | (nums[4]=5 > 3, stop) | [4, 5] | front 4 ≤ 5-3=2? no | nums[4] = 5 |
| 6 | 6 | pop 5, pop 4 (both ≤ 6) | [6] | front 6 ≤ 6-3=3? no | nums[6] = 6 |
| 7 | 7 | pop 6 (nums[6]=6 ≤ 7) | [7] | front 7 ≤ 7-3=4? no | nums[7] = 7 |
Final result across the recorded window maxes: [3, 3, 5, 5, 6, 7] —
matching both earlier approaches, with the deque never holding more than 3
indices at once.
Edge cases: when k equals the array's length (example 2), the deque
simply accumulates indices (popping smaller ones as bigger ones arrive)
until the single window position is reached, and the front is read exactly
once. The front-expiry check (dq[0] <= i - k) only ever needs to remove
at most one stale index per step, since the window only advances by one
position at a time.
Complexity
Time O(n) - every index is pushed onto the deque at most once and popped from it at most once, from either end, across the entire run.
Space O(k) - the deque never holds more than k indices at a time, since it's kept trimmed to the current window's range.
from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque() # stores indices; values at those indices are decreasing
result = []
for i, num in enumerate(nums):
# Drop indices whose value can never be the max while num is around.
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
# Drop the front if it has fallen out of the current window.
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
if __name__ == "__main__":
print(Solution().maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(Solution().maxSlidingWindow([1], 1))RecapThe whole problem in a few lines, for the night before
- Spot it: the maximum of every window of size
kas it slides across an array - Idea: keep a deque of indices whose values are in decreasing order; the front is always the current maximum
- Cost: O(n) time, O(k) space, because each index enters and leaves the deque once
- Trap: storing values instead of indices, so you can't tell when the front has slid out of the window
Interview follow-ups
What if you needed the rolling *minimum* instead of the maximum?
Flip the comparison in the deque's cleanup step: instead of popping values that are less than or equal to the new one, pop values that are greater than or equal to it, keeping the deque increasing from front to back instead of decreasing. Everything else about the algorithm — the window expiry check, the O(n) time bound — stays exactly the same.
The readings arrive as a live stream rather than a fixed array, and you need the current window's maximum available at every moment, not just at the end.
The same monotonic deque works directly in a streaming setting: each new reading triggers the same back-cleanup and front-expiry steps, and the front of the deque is always readable as "the current maximum" at any instant, without needing to know how many more readings are still to come. The only change from the array version is that there's no upfront
nto loop over — the same per-reading logic just runs indefinitely as new values arrive.
Frequently asked questions
A value that's smaller than the newly arriving value, and appeared earlier in the array, is doomed the moment the bigger value shows up: as long as the bigger value is still inside the window, it will always beat the smaller one for "current maximum". By the time the bigger value eventually slides out of the window, the smaller value — which arrived even earlier — has already slid out too. So there's no future moment where the smaller value could win; discarding it early is always safe.
The front of the deque has to be checked for expiry — "has this entry's position fallen out of the current window?" — and that check needs to know where a value came from, not just what it was. Two equal values at different positions would be indistinguishable if only values were stored, making it impossible to tell which one (if either) has expired.
The heap discards entries lazily, only once they happen to bubble to the top — until then, they sit inside the heap taking up space and adding to every future push/pop's O(log n) cost, since the heap's size (and thus its depth) is affected by how many stale entries are still sitting inside it. The deque, by contrast, throws away useless entries immediately and permanently the moment a bigger value arrives, so it never carries dead weight — its size never exceeds k, keeping every operation to O(1) amortized instead of O(log n).
A rolling maximum over a moving window is exactly a moving-window alert threshold: the worst reading in the last k data points for CPU load, queue depth, or latency, recomputed efficiently as each new reading comes in rather than rescanning the whole window from scratch every time.