The Hard Problem: Sliding Window Max

Given an array [1, 3, -1, -3, 5, 3, 6, 7] and window size k = 3. Find the max value in each window as it slides right.

• Window 1 [1, 3, -1]: Max = 3
• Window 2 [3, -1, -3]: Max = 3
• Window 3 [-1, -3, 5]: Max = 5

1. Naive Approach

For each window, scan for max.

• Time: O(N * K).
• Space: O(1).
• Result: Time Limit Exceeded for large inputs.

2. Optimal Approach: Monotonic Deque

We need a structure that gives us the max in O(1). A Deque (Double-Ended Queue) stores indices of “promising” candidates.

Rules:

1. Remove Old: If the index at the front is out of the window (i - k), pop front.
2. Maintain Order: Before pushing current x, pop everything from the back that is smaller than x. (Why keep a small number if a newer, larger number exists?)
3. Result: The front of the deque is always the max for the current window.

Interactive: Deque Visualizer

Watch how candidates are added and removed.

Array (Window K=3)

Deque (Indices)

Result

Start...

3. Implementation

Java

public int[] maxSlidingWindow(int[] nums, int k) {
  if (nums == null || k <= 0) return new int[0];
  int n = nums.length;
  int[] res = new int[n - k + 1];
  int ri = 0; // result index

  Deque<Integer> q = new ArrayDeque<>(); // Stores indices

  for (int i = 0; i < n; i++) {
    // 1. Remove out of bounds
    while (!q.isEmpty() && q.peek() < i - k + 1) {
      q.poll();
    }
    // 2. Remove smaller elements from back
    while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
      q.pollLast();
    }

    q.offer(i);

    if (i >= k - 1) {
      res[ri++] = nums[q.peek()];
    }
  }
  return res;
}

Go

func maxSlidingWindow(nums []int, k int) []int {
  if len(nums) == 0 { return []int{} }
  var res []int
  var q []int // Indices

  for i, n := range nums {
    // 1. Remove out of bounds
    if len(q) > 0 && q[0] < i-k+1 {
      q = q[1:]
    }
    // 2. Remove smaller
    for len(q) > 0 && nums[q[len(q)-1]] < n {
      q = q[:len(q)-1]
    }
    q = append(q, i)

    if i >= k-1 {
      res = append(res, nums[q[0]])
    }
  }
  return res;
}