Sliding Window Maximum - Solution & Explanation
Problem Statement
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.length
Approach Overview
Problem 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 1: Approach 1: Brute Force
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.
Complexity
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.
Approach 2: Approach 2: Optimized Deque Method
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.
Complexity
Time complexity: O(n), where n is the number of elements.
Space complexity: O(k) for the deque.
Approach 3: Priority Queue (Max-Heap)
We can use a priority queue (max-heap) to maintain the maximum value in the sliding window.
First, add the first k-1 elements to the priority queue. Then, starting from the k-th element, add the new element to the priority queue and check if the top element of the heap is out of the window. If it is, remove the top element. Then, add the top element of the heap to the result array.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array.
Approach 4: Monotonic Queue
To find the maximum value in a sliding window, a common method is to use a monotonic queue.
We can maintain a queue q that is monotonically decreasing from the front to the back, storing the indices of the elements. As we traverse the array nums, for the current element nums[i], we first check if the front element of the queue is out of the window. If it is, we remove the front element. Then, we compare the current element nums[i] with the elements at the back of the queue. If the elements at the back are less than or equal to the current element, we remove them until the element at the back is greater than the current element or the queue is empty. Then, we add the index of the current element to the queue. At this point, the front element of the queue is the maximum value of the current sliding window. Note that we add the front element of the queue to the result array when the index i is greater than or equal to k-1.
The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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. |
| Priority Queue (Max-Heap) | — |
| Monotonic Queue | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Sliding Window Maximum - Monotonic Queue - Leetcode 239 • NeetCode • 417,458 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sliding Window Maximum easy or hard?
How to solve Sliding Window Maximum in O(n)?
Sliding Window Maximum Python or Java solution?
What is the best approach for Sliding Window Maximum?
Is Sliding Window Maximum asked at Google/Amazon/Meta?
What data structure is used in Sliding Window Maximum?
What is the time complexity of Sliding Window Maximum?
Ready to solve this problem?
Practice Sliding Window Maximum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor