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.