Sliding Window Maximum Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: Array, Queue, Sliding Window, Monotonic Queue
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.
Examples
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]
Explanation: There is only one element in the array and window size is 1.
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Explanation: Each window contains one element.
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Explanation: There is only one window with size 2.
Intuition
The key insight is to use a monotonic queue (deque) that maintains elements in decreasing order. This allows us to efficiently find the maximum element in the current window and remove elements that are no longer in the window.
Approach
Approach 1: Monotonic Queue (Optimal)
1. Use a deque to maintain indices of elements in decreasing order
2. Remove elements from front that are outside the current window
3. Remove elements from back that are smaller than the current element
4. Add current element to the back
5. The front of deque always contains the maximum element
Approach 2: Max Heap
1. Use a max heap to keep track of elements in the current window
2. Remove elements that are outside the window
3. Extract maximum from heap for each window
4. Less efficient due to heap operations
Approach 3: Brute Force
1. For each window, find the maximum element
2. Simple but inefficient for large arrays
3. Time complexity O(n*k)
Dry Run
Let's trace through Example 1: nums = [1,3,-1,-3,5,3,6,7], k = 3
Monotonic Queue Approach:
- Window [1,3,-1]: deque = [1,3], max = 3
- Window [3,-1,-3]: deque = [3], max = 3
- Window [-1,-3,5]: deque = [5], max = 5
- Window [-3,5,3]: deque = [5], max = 5
- Window [5,3,6]: deque = [6], max = 6
- Window [3,6,7]: deque = [7], max = 7
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Monotonic Queue (Optimal)
Time Complexity: O(n) - Each element is pushed and popped at most once
Space Complexity: O(k) - Deque size is at most k
Solution 2: Max Heap
Time Complexity: O(n log k) - Heap operations
Space Complexity: O(k) - Heap size
Solution 3: Brute Force
Time Complexity: O(n*k) - For each window, find maximum
Space Complexity: O(1) - Constant extra space