LeetCode 239 · Hard · Sliding Window

Sliding Window Maximum

A window of size k slides across nums one step at a time. Return the largest value inside the window at every position.

O(n)time
O(k)space · the deque
monotonic dequevalues decrease front to back

nums: 1–16 integers, −99 to 99 · k: 1 to the length of nums

q deque of indices · value on top, index below · values strictly fall from front to back, so the front is the window max

output

public int[] maxSlidingWindow(int[] nums, int k) { int[] output = new int[nums.length - k + 1]; Deque<Integer> q = new ArrayDeque<>(); // indices, values falling int l = 0; int r = 0; while (r < nums.length) { while (!q.isEmpty() && nums[q.peekLast()] < nums[r]) { q.pollLast(); // can never be a max again } q.addLast(r); if (l > q.peekFirst()) { q.pollFirst(); // slid out of the window } if (r + 1 >= k) { output[l] = nums[q.peekFirst()]; l++; } r++; } return output;}
l
—
r
—
q
[]
output
[]

Why it works

  1. Brute force scans each window for its max: O(n · k). A heap of (value, index) pairs with lazy deletion gets O(n log n).
  2. A smaller value to the left is dead. Once nums[r] arrives, any earlier smaller value leaves the window first and is always outshone, so it can never be a max again. Popping those keeps the deque's values falling from front to back, and the front is the window max.
  3. Why O(n): every index is appended once and popped at most once, from one end or the other. The deque holds at most k indices, plus the new one for a moment before the stale front is dropped.
  4. Pitfall: store indices, not values. The front must be dropped when its index slides out (l > q.peekFirst()), and with repeated values only the index can tell copies apart.
  5. Strict <: equal values stay in the deque. Popping them with <= is also correct; it just keeps fewer entries.
  6. Related: the same monotonic idea, with a stack instead of a deque, drives Daily Temperatures and Largest Rectangle in Histogram.