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.
This approach involves checking each possible window (of length k) one by one and calculating the maximum for each window. This method is straightforward but inefficient for large arrays as it runs in O(n*k) time complexity.
This C solution iteratively evaluates each window by checking each element individually to find the maximum. It requires nested loops where one iterates through each window starting point and the other iterates within the window to find the maximum.
Time complexity: O(n*k), where n is the number of elements.
Space complexity: O(1) for storing the maximum of each window in output array.
Use a deque (double-ended queue) to store indices of array elements, which helps in maintaining the maximum for the sliding window in an efficient manner. As the window slides, the method checks and rearranges the deque so that the front always contains the index of the maximum element.
This C program uses a circular array-based deque to store indices. The deque is created such that the maximum element's index is always at the front and other elements are stored in a way that elements outside the window or smaller than the current maximum are removed efficiently.
Time complexity: O(n), where n is the number of elements.
Space complexity: O(k) for the deque.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time complexity: O(n*k), where n is the number of elements. |
| Approach 2: Optimized Deque Method | Time complexity: O(n), where n is the number of elements. |
| 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 |
Sliding Window Maximum - Monotonic Queue - Leetcode 239 • NeetCode • 393,937 views views
Watch 9 more video solutions →Practice Sliding Window Maximum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor