239. Sliding Window Maximum
Asked at Amazon, Microsoft, Walmart, NVIDIA and 2 more
Difficulty
Hard
Time
O(n)
Space
O(k)
Pattern
Array
Companies
6
Problem
You get an integer array nums and a window size k. Imagine a window of exactly k positions that starts at the left end of the array and slides one step to the right until it reaches the right end. At every position, look at the k numbers inside the window and take the largest one.
Return an array that holds the maximum of each window, in the order the windows appear. The answer has nums.length - k + 1 entries, one per window position.
A window may contain negative numbers, so do not assume the maximum is positive. If k equals the array length there is only one window, and the answer is a single number.
One max per window position
Constraints
- ●
1 <= nums.length <= 10^5 - ●
-10^4 <= nums[i] <= 10^4 - ●
1 <= k <= nums.length
Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]nums = [1], k = 1[1]Asked At
6 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Walmart | Hard | View all Walmart questions → |
| NVIDIA | Hard | View all NVIDIA questions → |
| DE Shaw | Hard | View all DE Shaw questions → |
| JPMorgan | Hard | View all JPMorgan 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.
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.
Monotonic deque of indices
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
O(n) timefrom 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 runs in O(n) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Sliding Window Maximum?
Sliding Window Maximum is asked at Amazon, Microsoft, Walmart, NVIDIA, DE Shaw, JPMorgan. 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.