Sliding Window Maximum | Stack and Queue

Finding the maximum element within every sliding window of size $K$ across an array is a classic algorithmic problem. This chapter explores how to transition from a naive $O(N \times K)$ quadratic approach to an optimal $O(N)$ linear time solution using a Monotonic Deque.

1. Problem Statement & Core Objective

Given an integer array (nums) and an integer window size ($K$), our objective is to slide a window of size $K$ from the extreme left to the extreme right of the array, one element at a time, and collect the maximum element from each window into a resulting list or array.

Example Walkthrough

Consider the array: [1, 3, -1, -3, 5, 3, 6, 7], with $K = 3$.

• Window 1: [1, 3, -1] $\rightarrow$ Maximum = 3
• Window 2: [3, -1, -3] $\rightarrow$ Maximum = 3
• Window 3: [-1, -3, 5] $\rightarrow$ Maximum = 5
• Window 4: [-3, 5, 3] $\rightarrow$ Maximum = 5
• Window 5: [5, 3, 6] $\rightarrow$ Maximum = 6
• Window 6: [3, 6, 7] $\rightarrow$ Maximum = 7

Resulting Maximum Array: [3, 3, 5, 5, 6, 7]

2. Naive Approach & Its Limitations

The most intuitive way to solve this problem is to simulate the sliding windows directly using nested loops.

Algorithm Design

1. Initialize an empty list to store window maximums.
2. Outer loop: Iterate from index i = 0 to n - K (representing the starting index of each window).
3. Inner loop: Scan through the $K$ elements from index i to i + K - 1 to find the maximum value (Maxi).
4. Append Maxi to the result list and return it once all windows are processed.

Naive Code Implementation (Java/Pseudo-code)

public List<Integer> maxSlidingWindowNaive(int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    int n = nums.length;
    
    for (int i = 0; i <= n - k; i++) {
        int maxi = nums[i];
        for (int j = i; j < i + k; j++) {
            maxi = Math.max(maxi, nums[j]);
        }
        result.add(maxi);
    }
    return result;
}

Complexity Analysis

• Time Complexity: $O((N - K + 1) \times K) \approx O(N \times K)$. For each of the $N - K$ windows, we re-scan $K$ elements. This results in quadratic time performance when $K \approx N$.
• Space Complexity: $O(N - K)$ to store the output window maximums.
• Why Interviewers Reject This: An interviewer will expect an optimized linear time solution ($O(N)$) because re-scanning overlapping elements in every window is redundant.

3. Transitioning to an Optimal Solution ($O(N)$)

To achieve an optimal $O(N)$ time complexity, we must adhere to two golden rules during a single traversal of the array:

1. Keep Only Window Elements: Out-of-bound elements (indices falling outside the current window of size $K$) must be purged instantly.
2. Eliminate Redundant Smaller Elements: If a newly encountered element is greater than or equal to preceding elements in the current window, those smaller elements can never serve as a maximum for current or future windows. They should be purged.

To satisfy both requirements efficiently, we need a data structure that permits insertions and deletions from both ends in $O(1)$ constant time: a Double-Ended Queue (Deque).

4. Understanding the Monotonic Deque Data Structure

A standard stack only allows pushes and pops from one end. A Deque (Double-Ended Queue) allows operations at both the front and the back:

Why a Deque Fits Our Needs

• Right End (Back): Acts like a stack. We use it to maintain a monotonic decreasing order of values by popping elements that are smaller than the incoming element.
• Left End (Front): Stores the index of the current window's maximum element at the very front, and allows us to remove indices that fall outside the left boundary of our sliding window.

5. Step-by-Step Dry Run

Let's trace nums = [1, 3, -1, -3, 5, 3, 6, 7], $K = 3$ using a Deque storing indices (whose values follow a decreasing order).

6. Complete Optimized Code Implementation

Here is the complete, production-grade algorithm implemented in Java using a Deque:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k == 0) return new int[0];
        
        int[] result = new int[n - k + 1];
        int resIndex = 0;
        
        // Deque to store indices of array elements
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 1. Remove indices that are out of the current window bounds (i - k)
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            
            // 2. Remove elements from the back that are smaller than the current element
            // (Maintaining a monotonic decreasing order)
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            
            // 3. Push current index into the deque
            deque.offerLast(i);
            
            // 4. Record the maximum for the current window once the first window of size K is formed
            if (i >= k - 1) {
                result[resIndex++] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

7. Complexity Analysis of Optimal Solution

8. Summary and Key Takeaways

• Problem Recognition: Whenever an interview problem asks for the maximum or minimum of sliding subarrays or windows in constant or linear time, immediately think of a Monotonic Stack/Deque.
• Monotonic Decreasing Strategy: Storing elements in decreasing order ensures that the absolute largest candidate for the current window is always instantly accessible at the front of the queue (peekFirst()).
• Deque Dual Utility: Utilizing a Double-Ended Queue allows the structure to operate as a stack from the back (for filtering smaller elements) while purging expired window boundaries from the front in $O(1)$ time.
• Store Indices, Not Values: Storing indices inside the Deque rather than raw values is essential so we can calculate window boundaries (i - k) and check element expiration accurately.
• Linear Efficiency: The optimal approach completely eliminates redundant inner loops, reducing time complexity from $O(N \times K)$ down to a clean, highly efficient $O(N)$.