Sliding Window Maximum
Asked at Amazon, Microsoft, Walmart
Problem
Given an array and a window size k, return the maximum value in each sliding window of size k. The monotonic deque approach achieves O(n) time, far better than the naive O(nk) or O(n log k) heap approach.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
Brute force: for each window, scan k elements to find the max. O(nk) total. Too slow for large inputs.
Better: use a max-heap of size k. For each window, push the new element and pop the old one. O(n log k). Still not optimal.
Optimal: monotonic deque. Maintain a deque of indices where values are in decreasing order. The front of the deque is always the current window max.
Why the deque works: when a new element arrives, pop all smaller elements from the back. They can never be the max while the new element is in the window. This keeps the deque monotonic decreasing.
Visual walkthrough for [1,3,-1,-3,5,3,6,7], k=3:
i=0: deque=[0(1)]. Window: [1]
i=1: 3>1, pop 0. deque=[1(3)]. Window: [1,3]
i=2: -1<3, push. deque=[1(3),2(-1)]. Window: [1,3,-1]. Max=deque[0]=3.
i=3: -3<-1, push. deque=[1(3),2(-1),3(-3)]. Remove index 0 (out of window). Max=3.
i=4: 5>-3,-1,3, pop all. deque=[4(5)]. Remove index 1 (out of window). Max=5.
i=5: 3<5, push. deque=[4(5),5(3)]. Max=5.
i=6: 6>3,5, pop all. deque=[6(6)]. Remove index 4 (out of window). Max=6.
i=7: 7>6, pop all. deque=[7(7)]. Max=7.
Result: [3,3,5,5,6,7]
Edge cases: k=1 (return the array itself), k=n (return global max), all same elements.
Optimal Approach
Use a deque storing indices (not values) in decreasing value order.
For each element:
- Remove indices from the back while the back value <= current value (maintains decreasing order).
- Push current index to the back.
- Remove the front if it is out of the window (index <= i - k).
- If i >= k - 1, record
deque[0]as the window max.
The deque front always holds the index of the current window max. Elements are removed from the back when a larger element arrives (they can never be the max again). Elements are removed from the front when they slide out of the window.
Time: O(n) — each element is pushed and popped at most once. Space: O(k) for the deque.
What Trips People Up in Real Interviews
Using a max-heap instead of a monotonic deque. A heap gives O(n log k), but the deque approach is O(n) because each element is pushed and popped at most once.
Storing values in the deque instead of indices. You need indices to check if the front element is still within the sliding window (index <= i - k).
Forgetting to remove out-of-window elements from the front. The front index might be older than i - k, meaning it has slid out of the current window.
Not popping smaller elements from the back. If you keep all elements, the deque is not monotonic and you can't guarantee the front is the max.
Returning the deque front value directly without checking if it is in the window. Always check dq[0] <= i - k before recording the max.
Solution Code
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque()
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 resultFrequently Asked Questions
What is the Sliding Window Maximum problem?
Given an array and a window size k, return the maximum value in each sliding window of size k. The `monotonic deque` approach achieves `O(n)` time, far better than the naive `O(nk)` or `O(n log k)` heap approach.
How do you solve Sliding Window Maximum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sliding Window Maximum?
Sliding Window Maximum is asked at Amazon, Microsoft, Walmart. It is a hard difficulty problem.
What are common mistakes on Sliding Window Maximum?
- Using a `max-heap` instead of a `monotonic deque`. A heap gives `O(n log k)`, but the `deque` approach is `O(n)` because each element is pushed and popped at most once.
- Storing values in the `deque` instead of indices. You need indices to check if the front element is still within the sliding window (index <= i - k).
- Forgetting to remove out-of-window elements from the front. The front index might be older than i - k, meaning it has slid out of the current window.
- Not popping smaller elements from the back. If you keep all elements, the `deque` is not monotonic and you can't guarantee the front is the max.
- Returning the `deque` front value directly without checking if it is in the window. Always check `dq[0] <= i - k` before recording the max.