The Hard Problem: Sliding Window Max

Imagine you are monitoring a real-time stock ticker or analyzing network traffic spikes. You receive a continuous stream of data points and need to constantly report the maximum value observed within the last k seconds (a rolling or “sliding” window).

The Problem Statement: Given an array of integers nums and an integer k (the window size), return an array of the maximum values in each sliding window of size k as it moves from the far left to the far right of the array.

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
…and so on.

1. Naive Approach: The Brute Force

The most intuitive way to solve this is to simulate the sliding window exactly. For each position of the window, we iterate through its k elements to find the maximum.

Process:

Loop through the array from index 0 to n - k.
For each starting index i, loop from i to i + k - 1 and track the maximum value.
Store the maximum in our result array.

Complexity:

Time Complexity: $O(N \times K)$. For each of the $N - K + 1$ windows, we scan $K$ elements. If $N = 10^5$ and $K = 5 \times 10^4$, this takes $5 \times 10^9$ operations, resulting in a Time Limit Exceeded (TLE).
Space Complexity: $O(1)$ (excluding the output array).

We need a structure that gives us the max in $O(1)$ time as the window slides.

2. Intuition & Analogy: The “Up-and-Coming Athlete”

To optimize, let’s use an analogy. Imagine a college basketball team where we only care about the best player over a rolling 3-year window.

Rule 1: Graduation (Out of Window): Even if a player is the absolute best of all time, once their 3 years are up (they slide out of the window), they must be removed from consideration. We only track their “graduation year” (index).
Rule 2: The Dominant Freshman (Monotonic Property): If a new freshman joins the team and is immediately better than the current sophomores or juniors, those older, weaker players will never be the top player for the rest of their time in college. The freshman is both better and younger (will stay in the window longer). We can safely stop tracking the older, weaker players entirely.

This logic naturally maps to a Monotonic Deque (Double-Ended Queue). We store the indices of promising candidates. The values corresponding to these indices will always be strictly decreasing (monotonic).

The Deque Rules:

Remove Expired (Pop Front): If the index at the front of the deque is no longer in the current window (i.e., index < i - k + 1), remove it.
Maintain Monotonicity (Pop Back): Before adding the current element nums[i], remove everything from the back of the deque that is smaller than or equal to nums[i]. Why keep a small number if a newer, larger number just arrived?
Add Current (Push Back): Add the current index i to the back.
Extract Max: The front of the deque will always hold the index of the maximum value for the current window.

3. Interactive: Monotonic Deque Visualizer

Watch how candidates are added and removed as the window slides. Pay attention to how smaller elements are ejected from the back of the deque when a larger element arrives.

Array (Window K=3)

Deque (Indices)

Result

Start...

4. Edge Cases & Clarifying Questions

Before jumping into code in an interview, clarify the following constraints:

Empty Array or $K = 0$: Return an empty array.
$K = 1$: The window size is just one element, meaning the result is identical to the input array.
$K > N$: If the window size is larger than the array, the maximum of the entire array is returned (though typically, constraints state $1 \leq k \leq nums.length$).
All Elements Negative: Ensure initialization and comparisons handle negative integers correctly (avoid assuming $0$ as a default max).

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

  // Stores indices, not values!
  Deque<Integer> q = new ArrayDeque<>();

  for (int i = 0; i < n; i++) {
    // 1. Remove elements that are out of the current window from the front
    while (!q.isEmpty() && q.peek() < i - k + 1) {
      q.poll();
    }

    // 2. Remove smaller elements from the back (maintain monotonic decreasing order)
    while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
      q.pollLast();
    }

    // 3. Add current element's index to the deque
    q.offer(i);

    // 4. Once we have processed at least 'k' elements, the front holds the max for the window
    if (i >= k - 1) {
      res[ri++] = nums[q.peek()];
    }
  }

  return res;
}

Go

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

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

    // 2. Remove smaller elements from the back
    for len(q) > 0 && nums[q[len(q)-1]] < n {
      q = q[:len(q)-1]
    }

    // 3. Add current element's index
    q = append(q, i)

    // 4. Append max to result once the window size is met
    if i >= k - 1 {
      res = append(res, nums[q[0]])
    }
  }

  return res;
}

6. Complexity Analysis

Approach	Time Complexity	Space Complexity	Description
Brute Force	$O(N \times K)$	$O(1)$	Scans the whole window of size $K$ for every step of the array. Very slow for large $K$.
Monotonic Deque	$O(N)$	$O(K)$	Each element is pushed and popped at most once, making it incredibly efficient. Space is bounded by $K$ since the deque never exceeds the window size.

Sliding Window Maximum