Sliding Window Maximum Lecture Notes

Problem Statement

Given an array and a number K, find the maximum value in every sliding window of size K in the array.

Problem Explanation

First Window: Calculate the maximum in the first K elements.
Next Windows: Slide the window by one position and compute the maximum again.
Continue this until the end of the array.
Example: For array [1, 3, -1, -3, 5, 3, 6, 7] and K=3:
- Window [1, 3, -1] → Maximum = 3
- Window [3, -1, -3] → Maximum = 3
- Window [-1, -3, 5] → Maximum = 5
- etc.

Brute Force Solution

Idea: Iterate through all possible windows and find the maximum for each.
Algorithm:
1. Start from index 0.
2. For each window, traverse the next K elements to find the maximum.
3. Repeat until the last possible window, i.e., index n-k.
Time Complexity: O((n-k) * k) = O(nk).
Space Complexity: O(n-k) - Storage for output list.*

Optimized Solution

Objective: Achieve O(n) runtime complexity using a single pass.
Key Insight: Maintain a data structure to track the maximum element efficiently.

Using Deque (Double-ended queue)

Maintaining Window Elements: Keep only the elements of the current window.
- Add new elements to the deque.
- Remove elements not within the window.
Monotonic Decreasing Order:
- Maintain the elements in decreasing order in the deque.
- Remove elements less than the current element from the deque.
Deque Operations:
- Push from the back for new elements.
- Pop from the front for elements outside the window.
- Pop from the back for maintaining decreasing order.
Steps:
1. Initialize an empty deque and a result list.
2. Traverse the array.
3. For each element:
  - Remove elements outside the window.
  - Maintain the decreasing order by removing smaller elements from the back.
  - Insert the current element's index.
  - For valid windows, append the maximum (front of deque) to the result list.
4. Return the result list.
Time Complexity: O(n) - Each element is pushed and popped at most once.
Space Complexity: O(k) - Deque stores window elements of size k.

Pseudocode

function sliding_window_maximum(array, k):
    result = []
    deque = []
    
    for i in range(len(array)):
        # Remove elements not within the window
        if deque and deque[0] <= i - k:
            deque.pop(0)
        
        # Maintain monotonic decreasing order
        while deque and array[deque[-1]] <= array[i]:
            deque.pop()
        
        # Insert current element
        deque.append(i)
        
        # Append max to result (deque's front element)
        if i >= k - 1:
            result.append(array[deque[0]])
    
    return result

Key Points

Use a deque to maintain window elements and their order.
Efficiently track the maximum of the window by maintaining a decreasing order.
Remove elements outside the window to keep the deque size optimal.

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(k)

Conclusion

Using a deque allows solving the sliding window maximum problem in linear time, making it efficient for larger data sets.