Sliding Window Maximum

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 <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

## Max Sliding Window

This problem asks us to find the maximum value within a sliding window of size `k` as it moves across an array `nums`. We need to return an array containing the maximum values for each window position.

### 1. Brute Force Solution

The simplest approach is to iterate through the array and, for each possible window, find the maximum value within that window. This involves nested loops.

```python
def max_sliding_window_brute_force(nums, k):
    n = len(nums)
    if n * k == 0:
        return []
    if k > n:
        return [max(nums)]

    result = []
    for i in range(n - k + 1):
        window = nums[i:i+k]
        result.append(max(window))
    return result

Example:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
max_sliding_window_brute_force(nums, k)  # Output: [3, 3, 5, 5, 6, 7]

2. Optimal Solution (Using a Deque)

A more efficient approach uses a double-ended queue (deque) to maintain a decreasing order of indices. The deque stores indices of potentially maximum elements within the current window.

from collections import deque

def max_sliding_window(nums, k):
    n = len(nums)
    if n * k == 0:
        return []
    if k > n:
        return [max(nums)]

    deque_val = deque()
    result = []

    for i in range(n):
        # Remove elements out of the window
        while deque_val and deque_val[0] <= i - k:
            deque_val.popleft()

        # Remove smaller elements in deque than current element
        while deque_val and nums[deque_val[-1]] < nums[i]:
            deque_val.pop()

        deque_val.append(i)

        # Add max to results
        if i >= k - 1:
            result.append(nums[deque_val[0]])

    return result

Explanation:

1. Initialization: Create a deque deque_val and a result list result. The deque will store indices.
2. Iteration: Iterate through the nums array.
   • Remove Out-of-Window Elements: If the leftmost element in the deque is outside the current window (i.e., deque_val[0] <= i - k), remove it from the left.
   • Maintain Decreasing Order: While the deque is not empty and the current element nums[i] is greater than the element at the index stored in the rightmost position of the deque, remove elements from the right of the deque. This ensures that the deque maintains a decreasing order of element values (from left to right).
   • Add Current Element's Index: Add the index i of the current element to the right of the deque.
   • Append Result: If the window has reached size k (i.e., i >= k - 1), append the element at the index stored in the leftmost position of the deque (which is the maximum element in the current window) to the result list.
3. Return: Return the result list.

Example:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
max_sliding_window(nums, k)  # Output: [3, 3, 5, 5, 6, 7]

3. Big(O) Run-time Analysis

• Brute Force: O(n*k), where n is the length of the array and k is the window size. This is because for each of the n-k+1 windows, we iterate through k elements to find the maximum.
• Optimal (Deque): O(n), where n is the length of the array. Each element is added and removed from the deque at most once.

4. Big(O) Space Usage Analysis

• Brute Force: O(n-k+1) as a list of size n-k+1 is created to store output.
• Optimal (Deque): O(k), where k is the window size. The deque stores at most k elements.

5. Edge Cases

• Empty Input Array: If the input array nums is empty, return an empty array.
• Window Size Greater Than Array Length: If k is greater than the length of nums, return an array containing the maximum element in nums.
• k = 1: The result is the original nums.
• Array with duplicate max values: Deque solution handles duplicates correctly by keeping all possible candidates within the window size. If the max value gets out of the window, the next largest value that might be a duplicate then becomes the new max.

Here's a summary: