MANG Problem #6: Sliding Window Maximum (Hard)

1. 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 the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

2. Approach: Monotonic Deque (O(n))

graph LR
    subgraph "Monotonic Deque (Indices)"
        D[Front: Max] --- D1[Index 1] --- D2[Index 2] --- D3[Back: Smallest]
    end
    
    Window[Sliding Window] --> Deque
    New[New Element] --> Check{Larger than Back?}
    Check -- Yes --> PopBack[Pop Back] --> New
    Check -- No --> PushBack[Push Back]

The Naive Way (O(N*K))

For every window position, iterate through all $K$ elements to find the max.

Why it fails: When $N=10^5$ and $K=10^4$, we do $10^9$ operations.

The Optimized Way: Monotonic Deque

We need a way to find the max in $O(1)$ and update it in $O(1)$. We use a Deque (Double-ended queue) to store indices of elements. We maintain the property that the elements at these indices are in strictly decreasing order.

Pop from Back: Before adding a new element, remove all indices from the back whose values are smaller than the current element (they will never be the max again).
Add to Back: Add the current index.
Pop from Front: If the index at the front is outside the window range, remove it.
Result: The element at deque.peekFirst() is always the maximum for the current window.

3. Java Implementation

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int n = nums.length;
    int[] result = new int[n - k + 1];
    int ri = 0;
    
    // Store indices
    Deque<Integer> q = new ArrayDeque<>();
    
    for (int i = 0; i < nums.length; i++) {
        // 1. Remove indices of elements smaller than current from back
        while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
            q.pollLast();
        }
        
        // 2. Add current index
        q.offer(i);
        
        // 3. Remove index if it's outside the window
        if (q.peekFirst() == i - k) {
            q.pollFirst();
        }
        
        // 4. If window is full, add front to result
        if (i >= k - 1) {
            result[ri++] = nums[q.peekFirst()];
        }
    }
    return result;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: If you have a new number that is larger than the existing numbers in the window, those smaller numbers are useless. They will never be the maximum because the new larger number will stay in the window longer than they will.
The Deque Strategy: By removing smaller elements from the back, we ensure the "King" (the largest) is always at the front.
The Cleanup: As the window moves, the "King" might get too old. We check the index at the front; if it's older than i - k, we "dethrone" it.

5. Interview Discussion

Interviewer: "Why store indices instead of values?"
You: "Indices allow us to easily check if the element has fallen out of the window's range."
Interviewer: "Can you use a Priority Queue?"
You: "Yes, but that would be $O(N \log N)$ because removing an arbitrary element from a heap takes $O(K)$. The Monotonic Deque gives us the optimal $O(N)$ solution."