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 an array containing the max sliding window.

Additional information

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

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]

Brute Force

Intuition
The simplest approach is to iterate through the array with a loop. For every position i from 0 to n-k, we simply look at the slice nums[i : i+k] and find the maximum value using the built-in max() function.

Algorithm

1. Initialize an empty list res.
2. Iterate i from 0 to len(nums) - k.
3. Find max_val = max(nums[i : i + k]).
4. Append max_val to res.
5. Return res.

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    if n * k == 0:
        return []
    
    output = []
    for i in range(n - k + 1):
        max_val = max(nums[i:i+k])
        output.append(max_val)
        
    return output

Time & Space Complexity

• Time complexity: O(n * k)

• Reason: For each of the n-k+1 windows, we scan k elements to find the maximum.

• Space complexity: O(1)

• Reason: Excluding the output list, we use constant extra space.

Monotonic Queue (Deque) - Optimal

Intuition
To improve efficiency, we need a way to access the maximum in O(1) time. A simple queue or list is insufficient. We can use a Deque (Double-Ended Queue) to maintain a list of indices of useful elements.

We want the deque to be monotonic decreasing, meaning the indices in the deque correspond to values that are strictly decreasing. The front of the deque will always hold the index of the maximum element for the current window.

1. Remove old indices: If the index at the front of the deque is outside the current window (i - k), pop it.
2. Maintain monotonicity: Before adding a new index i, remove all indices from the back of the deque whose values are smaller than nums[i] (because nums[i] is newer and larger, so the smaller old values will never be the maximum again).
3. Add new index: Push i to the back.
4. Record result: If i >= k - 1, the front of the deque is the max for this window.

Algorithm

1. Initialize a deque q (stores indices) and a list res (stores max values).
2. Iterate i through nums.
3. Clean Left: If q is not empty and q[0] == i - k, pop left (remove index that slid out of the window).
4. Clean Right: While q is not empty and nums[q[-1]] < nums[i], pop right (remove elements smaller than current, as they are useless).
5. Append i to q.
6. If i >= k - 1, append nums[q[0]] to res.
7. Return res.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    q = deque()
    res = []
    
    for i in range(len(nums)):
        # Remove indices that are out of the bounds of the sliding window
        if q and q[0] == i - k:
            q.popleft()
            
        # Remove indices whose corresponding values are less than nums[i]
        while q and nums[q[-1]] < nums[i]:
            q.pop()
            
        q.append(i)
        
        # Add the maximum element of the current window to the result
        if i >= k - 1:
            res.append(nums[q[0]])
            
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each element is added to the deque exactly once and removed at most once. The operations inside the loop are amortized O(1).

• Space complexity: O(k)

• Reason: The deque stores at most k indices (in the worst case where the array is sorted descending).