The Hard Problem: Sliding Window Max

[!NOTE] This module explores the core principles of the Sliding Window Maximum problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

Given an array 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.

Example: Given nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3.

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

Edge Cases & Clarifying Questions

• Empty array (nums.length == 0): What should be returned? (Return an empty array).
• k = 1: The sliding window size is 1, so the maximum of each window is the element itself. Return the original array.
• Negative Numbers: The array can contain negative numbers. Ensure that the initial maximum isn’t incorrectly set to 0.
• k > nums.length: Often k is constrained to 1 <= k <= nums.length, but if k exceeds the array size, return the maximum of the entire array.

---

2. Interactive Analysis

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. Solutions

Intuition (The “Genesis”)

Brute Force Approach: The most straightforward way is to iterate through each window of size k and find the maximum element. Since there are N - k + 1 windows and finding the maximum in each window takes O(k) time, the overall time complexity is O(N * K). This is too slow for large inputs.

Optimized Approach (Monotonic Deque): We want to find the maximum in O(1) time for each window, leading to an O(N) overall time complexity. The key insight is that if a number x is larger than all currently stored numbers y that came before it, then those y numbers can never be the maximum of the window again. Why? Because x is larger AND x will stay in the window longer than y. So we can safely discard y.

This property (maintaining elements in decreasing order) explicitly names the pattern: the Monotonic Deque (Double-Ended Queue). We store the indices of elements in the deque, ensuring the values they point to are strictly monotonically decreasing.

Common Pitfalls

• Storing Values instead of Indices: If you store values in the deque, you lose the ability to check if the maximum element (at the front of the deque) has fallen out of the sliding window. Always store indices.
• Not Popping Smaller Elements First: When adding a new element, you must pop all smaller elements from the back of the deque before pushing the new element. Failing to do this breaks the monotonic property.
• Handling Out-of-Bounds Elements: Forgetting to remove elements from the front of the deque when their indices are outside the current window (i - k).

Java

Go

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;
}

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;
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Naive	O(N * K)	O(1)	Repeatedly scanning the window.
Monotonic Deque	O(N)	O(K)	Each element is pushed and popped at most once.