Watch 10 video solutions for Sliding Window Maximum, a hard level problem involving Array, Queue, Sliding Window. This walkthrough by NeetCode has 305,027 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.lengthProblem Overview: You are given an array nums and a window size k. As the window slides from left to right, return the maximum element in each window of size k. The challenge is avoiding repeated work when the window shifts by one position.
Approach 1: Brute Force (Time: O(nk), Space: O(1))
The straightforward method evaluates every window independently. Iterate through the array and for each starting index i, scan the next k elements to compute the maximum. This uses simple iteration over the array and does not require extra data structures. While easy to implement and good for understanding the problem mechanics, it repeats comparisons for overlapping windows. With large inputs or large k, the repeated scanning causes the runtime to grow to O(nk), which fails typical interview constraints.
Approach 2: Optimized Deque Method (Time: O(n), Space: O(k))
The optimal solution maintains a decreasing monotonic queue using a deque. Store indices of elements, not the values themselves. While iterating through the array, remove indices from the front if they fall outside the current window. Then remove indices from the back while their corresponding values are smaller than the current element. This guarantees the deque stays in decreasing order of values. The front of the deque always holds the index of the current window's maximum. Each element is inserted and removed at most once, producing O(n) time complexity with O(k) space.
This method is a classic use of a sliding window combined with a queue-like structure. The key insight is maintaining candidates for the maximum while discarding elements that can never become maximums in future windows.
Recommended for interviews: Interviewers expect the monotonic deque solution. The brute force approach demonstrates baseline reasoning, but the optimized method shows mastery of sliding window patterns and amortized analysis. Being able to explain why each index enters and leaves the deque only once is the signal that you understand the optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(nk) | O(1) | Good for small inputs or quickly validating logic during early problem exploration |
| Monotonic Deque (Sliding Window) | O(n) | O(k) | Best general solution for large arrays and the expected approach in coding interviews |