Sliding Window Maximum
Problem Statement
You are given an integer array nums and an integer k. A sliding window of size k moves from the left side of the array to the right side, one index at a time. Return the maximum value in each window.
Input
An integer array nums and an integer k, the fixed window length.
Output
An integer array where each element is the maximum value for one contiguous window of length k.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4 - •
1 <= k <= nums.length
Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7], k = 3
[3,3,5,5,6,7]Example 2
nums = [1], k = 1
[1]Example 3
nums = [9,11], k = 2
[11]Learning Objectives
- Recognise when a fixed-size window needs the best value under constant movement.
- Maintain a monotonic decreasing deque of candidate maximum indices.
- Explain why dominated values can be discarded permanently from the back of the deque.
- Handle stale indices cleanly as the left edge of the window advances.
Intuition
This is a fixed-size sliding window problem, but the expensive part is not moving the window. The expensive part is repeatedly asking for the maximum inside it. Recomputing that maximum by scanning each window loses the core pattern and can degrade to quadratic work.
The pattern identification is a monotonic deque. The deque stores indices, not only values, because indices tell us when a candidate leaves the window. Values inside the deque are kept in decreasing order, so the front is always the current maximum. When a new value arrives, every smaller value behind it becomes useless: the new value is larger and will stay in the window longer. That is the key interview insight.
Common mistakes
- ×Storing values instead of indices, which makes it hard to know when a value leaves the window.
- ×Removing stale indices only after reading the maximum, causing expired values to appear in the answer.
- ×Keeping smaller values behind a new larger value even though they can never become maximum while the new value is present.
- ×Using a deque in increasing order by accident and reading the minimum instead of the maximum.
Algorithm Explanation
Window setup
Keep a deque of indices whose corresponding values are in decreasing order from front to back. The front index is the maximum for the current window. The current window ending at right starts at right - k + 1 once the first full window exists.
Window visualization
For nums = [1,3,-1,-3,5,3,6,7] and k = 3, start with index 0 in the deque as [0:1]. When index 1 with value 3 arrives, value 1 is smaller and sits behind a newer larger value, so it is popped and the deque becomes [1:3]. Index 2 with value -1 is added behind 3, producing the first output 3. At index 4, the old index 1 has left the window and the new value 5 removes -1 and -3 from the back, leaving [4:5]. The deque is always the compressed list of possible maximums.
Algorithm
- Create an empty deque of indices and an answer array of size n - k + 1.
- For each index right, first remove deque front indices that are outside the current window.
- While the deque back points to a value less than or equal to nums[right], remove it because the new value dominates it.
- Add right to the deque back.
- Once right >= k - 1, write nums[deque front] into the next answer slot.
- Return the answer array.
Solutions
Solution: Monotonic decreasing deque
The deque stores only candidates that can still become a window maximum. It removes stale indices from the front and removes dominated smaller values from the back, so each index is inserted once and removed at most once.
Step-by-step
- Allocate the result array with one slot per full window.
- Sweep right from 0 to n - 1.
- Remove any deque front index that is more than k positions behind right.
- Pop from the back while the incoming value is greater than or equal to the stored back value.
- Push the incoming index.
- After the first full window forms, read the maximum from the deque front.
O(n)
O(k)
Every index enters and leaves the deque at most once, and the deque holds only current-window candidates.
Java implementation
Dry Run
Sample input
nums = [1,3,-1,-3,5,3,6,7], k = 3. Trace the decreasing deque of index:value pairs after each right index is processed.
| right | nums[right] | left boundary | deque after processing | output appended |
|---|---|---|---|---|
| 0 | 1 | 0 | [0:1] | none |
| 1 | 3 | 0 | [1:3] | none |
| 2 | -1 | 0 | [1:3, 2:-1] | 3 |
| 3 | -3 | 1 | [1:3, 2:-1, 3:-3] | 3 |
| 4 | 5 | 2 | [4:5] | 5 |
| 5 | 3 | 3 | [4:5, 5:3] | 5 |
| 6 | 6 | 4 | [6:6] | 6 |
| 7 | 7 | 5 | [7:7] | 7 |
The output values are collected exactly when a full window exists: [3,3,5,5,6,7]. The deque never stores an index that is outside the current window or dominated by a newer larger value.
Interview Tips
Name the invariant early: indices in the deque are inside the window, and their values decrease from front to back. That one sentence explains why the front is the maximum and why back removals are safe. A max-heap can also solve the problem in O(n log n) with lazy removal, but the monotonic deque is the expected premium answer because it is linear.
Likely follow-ups
- How would you return the minimum for each window instead?
- How would you support both maximum and minimum queries for the same moving window?
- What changes if the window size varies instead of staying fixed?
- How would a heap-based solution remove stale indices lazily?
Similar Problems
Key Takeaways
- A monotonic deque is the linear-time structure for fixed-window maximums.
- Store indices so stale candidates can be removed as the window moves.
- A new larger value permanently dominates smaller values behind it.
- The deque front is always the answer for the current full window.