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.lengthThe Sliding Window Maximum problem asks you to find the maximum value in every contiguous subarray of size k. A brute force approach checks each window individually, leading to O(n*k) time, which is inefficient for large inputs.
The most efficient strategy uses a monotonic deque (double-ended queue). The deque stores indices of elements in decreasing order of their values. When the window moves forward, indices that fall outside the window are removed, and smaller elements are popped from the back to maintain the decreasing order. This ensures the front of the deque always holds the index of the current window's maximum.
An alternative solution uses a max heap (priority queue) to track the largest element in the window, though it requires extra work to discard outdated elements.
The monotonic queue approach achieves optimal performance with linear time complexity and is commonly expected in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Deque | O(n) | O(k) |
| Max Heap (Priority Queue) | O(n log k) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How about using a data structure such as deque (double-ended queue)?
The queue size need not be the same as the window’s size.
Remove redundant elements and the queue should store only elements that need to be considered.
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.
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.
1def maxSlidingWindow(nums, k):
2 result = []
3 for i in range(len(nums) - k + 1):
4 result.append(max(nums[i:i+k]))
5 return result
6
7# Example usage:
8nums = [1, 3, -1, -3, 5, 3, 6, 7]
9k = 3
10print(maxSlidingWindow(nums, k))In the Python solution, we use a list comprehension to evaluate each window, compute the maximum, and append to the result list, making use of the built-in max function.
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.
Time complexity: O(n), where n is the number of elements.
Space complexity: O(k) for the deque.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the problem can be solved using a max heap (priority queue). Each step inserts the new element and removes outdated ones, but the complexity becomes O(n log k), which is slower than the deque-based O(n) solution.
Yes, Sliding Window Maximum is a well-known interview problem frequently asked in FAANG and other top tech companies. It tests understanding of sliding window patterns and advanced data structures like monotonic queues.
A monotonic double-ended queue (deque) is the best data structure for this problem. It keeps elements ordered so the maximum element of the current window is always at the front, enabling efficient updates when the window shifts.
The optimal solution uses a monotonic deque that stores indices of elements in decreasing order. This structure allows constant-time access to the current window's maximum while maintaining efficient updates as the window slides. It achieves O(n) time complexity.
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.