Sliding Window Maximum

Hard

📘 Problem Statement

You are given an array of integers nums and an integer k. 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 maximum sliding window.

🔍 Example

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]

🧠 Key Insight

A naive approach would be to find the maximum in each window, but that would be O(n*k) which is inefficient.
We need a data structure that can efficiently:
1. Add new elements as the window slides
2. Remove elements that are no longer in the window
3. Find the maximum element in the current window
A deque (double-ended queue) can be used to maintain a monotonic decreasing queue of indices.
We only keep elements that could potentially be the maximum in future windows.

🧮 Monotonic Queue Technique

The key idea is to maintain a deque of indices such that:

Elements in the deque are in decreasing order of their values
The front of the deque always contains the index of the maximum element in the current window
When sliding the window, we remove indices that fall outside the window

🛠️ Solution

from collections import deque

def maxSlidingWindow(nums, k):
    result = []
    dq = deque()  # Will store indices
    
    for i in range(len(nums)):
        # Remove elements outside the window
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements as they won't be the maximum
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        # Add current element's index
        dq.append(i)
        
        # Add to result if we've reached window size
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

🕒 Time Complexity: $O(n)$ -> Each element is processed exactly once and each is added/removed from the deque at most once.

📦 Space Complexity: $O(k)$ -> The deque can contain at most k elements.

💡 Explanation

We use a deque to store indices of elements in the current window.
For each element at index i:
- Remove indices that are outside the current window (i-k+1 to i)
- Remove indices of smaller elements from the back of the deque (as they can’t be the maximum)
- Add the current index to the deque
- If we’ve processed at least k elements, add the maximum (front of deque) to the result
The deque maintains a monotonically decreasing order of values, ensuring the maximum is always at the front.

🔍 Visualization

Consider nums = [1,3,-1,-3,5,3,6,7] with k = 3:

i=0: Add index 0 to deque. deque=[0]
i=1: Remove nothing (1 < 3). Add index 1. deque=[1]
i=2: 3 > -1, so keep 1 in deque. Add index 2. deque=[1,2]
- Window complete, add nums[deque[0]] = nums[1] = 3 to result
i=3: Remove nothing. -1 > -3, so keep 2. Add index 3. deque=[1,2,3]
- Add nums[1] = 3 to result
i=4: Remove index 1 (outside window). Remove 2,3 (smaller values). Add index 4. deque=[4]
- Add nums[4] = 5 to result
i=5: Remove nothing. 5 > 3, so keep 4. Add index 5. deque=[4,5]
- Add nums[4] = 5 to result
i=6: Remove index 4 (outside window). Remove 5 (smaller value). Add index 6. deque=[6]
- Add nums[6] = 6 to result
i=7: Remove nothing. 6 < 7, so remove 6. Add index 7. deque=[7]
- Add nums[7] = 7 to result

Final result: [3,3,5,5,6,7]

📊 Priority Queue Approach

Another way to solve this problem is using a priority queue (max heap). The idea is to:

Keep a max heap of (value, index) pairs
Remove elements that are outside the current window
The top of the heap is always the maximum element in the current window

🛠️ Priority Queue Solution

import heapq

def maxSlidingWindow(nums, k):
    result = []
    # Use max heap (multiply by -1 since Python has min heap by default)
    heap = []
    
    for i in range(len(nums)):
        # Add current element to the heap
        heapq.heappush(heap, (-nums[i], i))
        
        # If we've reached window size
        if i >= k - 1:
            # Remove elements outside the current window
            while heap and heap[0][1] < i - k + 1:
                heapq.heappop(heap)
            
            # Add the maximum to result
            result.append(-heap[0][0])
    
    return result

🕒 Time Complexity: $O(n \log n)$ -> Each element is pushed and popped from the heap at most once, and each operation takes O(log n) time.

📦 Space Complexity: $O(n)$ -> In the worst case, all elements might be in the heap.

💡 Priority Queue Explanation

We use a max heap to store (value, index) pairs. Since Python’s heapq is a min heap, we negate the values to simulate a max heap.
For each element at index i:
- Add the current element to the heap
- If we’ve processed at least k elements:
  - Remove elements that are outside the current window
  - The top of the heap is the maximum element in the current window
The priority queue approach is more intuitive but less efficient than the monotonic queue approach.

🔄 Comparison of Approaches

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Monotonic Queue	O(n)	O(k)	More efficient	Slightly more complex to understand
Priority Queue	O(n log n)	O(n)	More intuitive	Less efficient

The monotonic queue approach is generally preferred due to its linear time complexity, but the priority queue approach is a good alternative if you’re more familiar with heap operations.