Sliding Window Maximum

1. Introduction: The Rolling Extreme

Imagine you are monitoring the stock market. You have a dashboard that only displays the highest stock price over the last 60 minutes. As every new minute ticks by, the 60-minute window slides forward. A new price enters the window, and an old price falls out of the window.

If the old price that fell out was the absolute maximum, you have a problem. You now need to know the second highest price in the window!

• Brute Force: Rescan the entire 60-minute window every single minute. $O(N \times K)$ time. Too slow.
• Max-Heap: Put the window in a Priority Queue. But removing the expired element takes $O(K)$. Time: $O(N \log K)$. Fast, but not optimal.

The absolute optimal solution uses a Monotonic Deque, which solves the problem in strict $O(N)$ time. This is a notorious FAANG interview question because it requires combining Sliding Window pointers with a complex data structure.

2. Core Concept: The Monotonic Deque

A Deque (Double-Ended Queue) allows insertions and removals from BOTH the front and the back in $O(1)$ time. "Monotonic" means strictly increasing or decreasing.

To maintain the maximum of a sliding window, we use a Monotonically Decreasing Deque. The rules:

1. The Deque stores indices, not values (because we need to know when an element expires and falls out of the window!).
2. The values corresponding to the indices in the Deque must be strictly decreasing.
3. The absolute Maximum value of the current window is always at the front of the Deque.

The Golden Rule: When a new element arrives, it violently kicks out any element smaller than it from the back of the Deque. Why? Because if a new element is larger than an older element, that older element can never be the maximum again for the rest of its lifespan! It is completely useless.

3. Advanced Code Example: Sliding Window Maximum

Problem Statement: (LeetCode 239) 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.

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int resultIndex = 0;
        
        // Deque stores INDICES, not values!
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 1. Remove expired elements from the FRONT of the deque
            // If the index at the front of the deque is outside our window [i - k + 1, i], it's dead.
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.pollFirst();
            }
            
            // 2. Maintain Monotonic Decreasing Order from the BACK
            // Destroy all older elements that are smaller than the current element.
            // They are useless because the current element is bigger AND will live longer!
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            
            // 3. Add the current index to the back
            deque.offerLast(i);
            
            // 4. Extract the answer
            // The window is fully formed once our index 'i' reaches 'k - 1'.
            if (i >= k - 1) {
                // The absolute maximum is ALWAYS at the front of our Monotonic Deque!
                result[resultIndex++] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Even though there is a while loop inside the for loop, every single index is pushed into the deque exactly once and popped exactly once. The amortized time is strictly $O(N)$.
• Space Complexity: $O(K)$ for the Deque, which stores at most $K$ indices.

4. Why Does This Work? (Mental Trace)

Let nums = [1, 3, -1, -3, 5, 3], k = 3.

1. i=0 (val = 1): Deque is empty. Add index 0. Deque: [0(val:1)].
2. i=1 (val = 3): 3 > 1. The 1 is useless. Pop 0. Add 1. Deque: [1(val:3)].
3. i=2 (val = -1): -1 <= 3. It doesn't beat the max, but it might be the max later after 3 expires! Add to back. Deque: [1(val:3), 2(val:-1)].
   • Window is size 3! Front is index 1 (val=3). Result = 3.
4. i=3 (val = -3): -3 <= -1. Add to back. Deque: [1(val:3), 2(val:-1), 3(val:-3)].
   • Front is index 1 (val=3). Result = 3.
5. i=4 (val = 5):
   • Expiration check: Index 1 is $4 - 3 = 1$. It expires! Pop front! Deque: [2(val:-1), 3(val:-3)].
   • Monotonic check: 5 > -3. Pop 3. 5 > -1. Pop 2. Add 4. Deque: [4(val:5)].
   • Front is index 4 (val=5). Result = 5.

5. Common Mistakes Beginners Make

1. Storing Values instead of Indices in the Deque

   • The Mistake: deque.offerLast(nums[i]);
   • Why it's wrong: You can't perform the Expiration Check. If the front of the deque is 5, how do you know if that 5 was from index 1 (expired) or index 3 (still valid)? You MUST store the index to calculate mathematical bounds (index == i - k).

2. Using .pop() instead of .pollLast()

   • The Mistake: Java's Deque API is confusing because it implements both Stack and Queue interfaces.
   • Why it's wrong: pop() removes from the front (Stack behavior). You need to purge weak elements from the back where the newest element is entering. Use pollLast() explicitly to avoid logical errors.

3. Using < instead of <= in the Monotonic check

   • The Mistake: while(nums[deque.peekLast()] < nums[i])
   • Why it's wrong: If you have duplicate maximums (e.g., [5, 5, 5]), and you only pop strictly smaller elements, your deque fills up with duplicates. While technically correct, it wastes memory. Popping <= ensures only the freshest, longest-living duplicate survives.

6. Interview Q&A

Q1: What if the problem asks for Sliding Window MINIMUM? Answer: The algorithm is 99% identical. You just change the while loop condition to while(nums[deque.peekLast()] >= nums[i]). You maintain a Monotonically Increasing deque, so the absolute smallest element is always at the front!

Q2: Can we solve this with Dynamic Programming? Answer: Yes! The Array Partition trick. You split the array into blocks of size K. You calculate the leftMax (max from start of block to i) and rightMax (max from i to end of block) for every element. The sliding window max for [i, j] is just Math.max(rightMax[i], leftMax[j]). It is mathematically brilliant and $O(N)$, but the Deque solution is heavily preferred in interviews.

7. Practice Problems

1. Sliding Window Maximum (LeetCode 239)
   • Goal: Master the 4-step Deque template perfectly.
2. Shortest Subarray with Sum at Least K (LeetCode 862 - Hard)
   • Hint: Combine a Prefix Sum Array with a Monotonically Increasing Deque! (This is an extremely elite problem).
3. Constrained Subsequence Sum (LeetCode 1425 - Hard)
   • Hint: 1D Dynamic Programming, where the DP transition requires finding the maximum of the last K states. Use the Sliding Window Maximum deque to optimize the DP from $O(N \times K)$ to $O(N)$!

8. Summary

• The Problem: Finding extreme values (Min/Max) inside a moving window.
• The Data Structure: Deque<Integer> storing indices.
• The Lifecycle:
  1. Purge expired indices from the front.
  2. Purge useless (smaller) indices from the back.
  3. Push the new index to the back.
  4. The answer is always at the front.

Advanced Code Implementations

// Example: Sliding Window Maximum using Deque
import java.util.*;

public class SlidingWindowMax {
    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;
        
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // Remove indices that are out of bound for the current window
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            
            // Remove smaller elements in k range as they are useless
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            
            q.offer(i);
            
            if (i >= k - 1) {
                result[ri++] = nums[q.peek()];
            }
        }
        return result;
    }
}

// Example: Sliding Window Maximum using Priority Queue (Less Optimal)
import java.util.*;

public class SlidingWindowMaxPQ {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }
        
        result[0] = pq.peek()[0];
        for (int i = k; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            result[i - k + 1] = pq.peek()[0];
        }
        return result;
    }
}

Expanded Interview Q&A

Q1: Why is Deque preferred over Priority Queue for this problem?

Answer: A Deque allows adding and removing elements from both ends in O(1) time, yielding an overall O(N) complexity. Priority Queue gives O(N log N) complexity.

Q2: What exactly does the Deque store in the optimal solution?

Answer: It stores the indices of array elements, not the values themselves. This makes it easy to check if an element is out of the sliding window bounds.

Q3: Why do we remove smaller elements from the back of the Deque?

Answer: Because if a new element is larger than previous ones in the window, those smaller previous elements can never be the maximum for any future window.

Q4: Is the Deque strictly monotonically decreasing?

Answer: Yes, the elements indexed by the Deque are strictly decreasing, which ensures the maximum element is always at the front.

Q5: How would you modify this to find the Sliding Window Minimum?

Answer: Just change the condition in the while loop to remove elements that are larger than the current element: nums[q.peekLast()] > nums[i].