How Do You Find the Maximum in Every Sliding Window of Size K?
Learn the monotonic deque technique to solve sliding window maximum in O(n) time for this common algorithms interview question.
Expected Interview Answer
You solve sliding-window-maximum in O(n) time using a monotonic deque that stores indices in decreasing order of their values, so the front of the deque is always the index of the current window’s maximum, popped and pushed at most once each as the window slides.
As the window slides one position at a time across the array, you maintain a deque of indices whose corresponding values are in strictly decreasing order from front to back. Before adding the current index, you pop from the back of the deque every index whose value is less than or equal to the current value, since those elements can never be the maximum again while the current, larger element is still in the window — this is what keeps the deque monotonic. You also check the front of the deque and pop it if its index has fallen outside the current window’s left boundary. After these two cleanup steps, the front of the deque always holds the index of the maximum for the current window, which you record once the window has grown to size k. Each index is pushed and popped from the deque at most once across the whole scan, which is why total work is O(n) despite sliding n - k + 1 windows, versus the naive O(n·k) approach of scanning every window fully or the O(n log k) heap-based approach that needs lazy deletion for expired indices.
- O(n) total time versus O(n·k) for a naive per-window scan
- Each array index enters and leaves the deque at most once
- No need for lazy deletion, unlike a heap-based alternative
- Deque stores indices, not values, so window-boundary checks are O(1)
AI Mentor Explanation
A selector tracking the fastest bowler among the last k overs keeps a shortlist ordered from fastest to slowest, but only ever needs to compare a new bowler against the back of the shortlist. When a new over’s bowler is faster than the bowler currently at the back of the shortlist, that slower bowler is removed, since they can never again be the fastest while this new, faster bowler is still within the last k overs — this repeats until the shortlist is back in strict fastest-to-slowest order. If the bowler at the front of the shortlist bowled more than k overs ago, they are dropped from the front since they have aged out of the window. The bowler now at the front of the shortlist is always the fastest among the last k overs, maintained with each bowler entering and leaving the shortlist only once across the whole match.
Step-by-Step Explanation
Step 1
Maintain a monotonic deque of indices
Indices in the deque correspond to strictly decreasing values, front to back.
Step 2
Trim the back before pushing
Pop indices from the back whose value is <= the current value; they can never win again.
Step 3
Push the current index
Add the current index to the back of the deque after trimming.
Step 4
Trim the front and record the max
Pop the front if its index is out of the window; once the window has size k, the front holds the maximum.
What Interviewer Expects
- Explain why the deque stays monotonically decreasing and why that guarantees correctness
- State the amortized O(n) complexity, with each index pushed and popped at most once
- Compare against the naive O(n·k) and the heap-based O(n log k) alternatives
- Correctly handle window-boundary eviction using indices, not values, stored in the deque
Common Mistakes
- Storing values instead of indices in the deque, losing the ability to check window boundaries
- Popping only once from the back instead of a while-loop, breaking the monotonic invariant
- Forgetting to evict the front index once it falls outside the window
- Recomputing the max by scanning the window each time, degrading to O(n·k)
Best Answer (HR Friendly)
“I keep a special queue of array indices that stays sorted from largest value to smallest as I slide the window. Before adding a new index, I remove any smaller values from the back since they can never be the max again once a bigger, more recent value is in the window, and I drop the front index once it slides out of the window. This means the front of the queue is always the current window’s maximum, and the whole scan only takes O(n) time total.”
Code Example
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values decreasing front to back
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]Follow-up Questions
- How would you adapt this to track the sliding window minimum instead?
- Why is the heap-based approach O(n log k) instead of O(n) like the deque approach?
- How would you find the sliding window median instead of the maximum?
- How does the amortized analysis prove O(n) total time despite the nested-looking while loop?
MCQ Practice
1. What invariant does the deque maintain in the sliding window maximum algorithm?
The deque holds indices whose values decrease from front to back, so the front index always holds the current window maximum.
2. What is the overall time complexity of the monotonic deque approach for n elements and window size k?
Each index is pushed and popped from the deque at most once across the entire scan, giving amortized O(n) total time.
3. Why does the algorithm store indices in the deque instead of values?
Storing indices lets the algorithm detect and evict the front element once it slides outside the k-sized window boundary.
Flash Cards
What does the deque store in the sliding window maximum algorithm? — Array indices, kept in strictly decreasing order of their values.
Why are smaller values popped from the back before pushing a new index? — They can never be the maximum again while a newer, larger value remains in the window.
What is the total time complexity across the whole array? — O(n) amortized, since each index enters and leaves the deque at most once.
When is the front of the deque evicted? — When its index falls outside the current window (index <= current index - k).