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: Given an integer array nums and a window size k, move a window of length k from left to right and report the maximum element inside each window. The window shifts one position at a time, so you must efficiently maintain the current maximum as elements enter and leave the window.
Approach 1: Brute Force (O(n * k) time, O(1) space)
The straightforward solution recomputes the maximum for every window independently. Iterate from index 0 to n - k, and for each position scan the next k elements to find the maximum. This uses only a few variables, so extra space stays constant. The drawback is the repeated work: every shift of the window triggers another k-length scan, leading to O(n * k) time complexity. This approach works when k is small or input size is limited, but it becomes slow for large arrays.
Approach 2: Optimized Deque Method (O(n) time, O(k) space)
The optimal solution uses a monotonic deque to track candidate maximum values for the current window. Instead of storing values, the deque stores indices in decreasing order of their corresponding array values. When processing a new element, remove indices from the back while their values are smaller than the current element. This keeps the deque decreasing, so the front always holds the index of the maximum element in the current window. Also remove the front index if it falls outside the window. Each element is inserted and removed at most once, which results in O(n) time and O(k) space.
This technique is a classic application of sliding window optimization combined with a queue-like structure. The decreasing order property turns the deque into a monotonic queue, allowing constant-time access to the maximum element.
Recommended for interviews: The monotonic deque approach is the expected solution in most interviews. Brute force shows that you understand the window movement, but the optimized method demonstrates algorithmic maturity and familiarity with advanced data structure patterns. Interviewers typically look for the insight that each element should be processed only once, which is exactly what the monotonic deque guarantees.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 Window Scan | O(n * k) | O(1) | Simple implementation when array size is small or window size is tiny |
| Monotonic Deque (Optimal) | O(n) | O(k) | Best for large arrays and interview settings where linear time is expected |
Sliding Window Maximum - Monotonic Queue - Leetcode 239 • NeetCode • 305,027 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