4.4 Sliding Window Maximum (Monotonic Deque)

Demo: Sliding Window Maximum — LC 239 (Hard — Google/Uber High)

Statement (Demo): Given an integer array nums and an integer k, return the maximum of every sliding window of size k. Example: nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7] | ⚡ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴

Approach: Keep indices in a deque with decreasing values — the front is always the window's max. Drop everything smaller than the new element from the back (they can never be the max again), and drop the front once it falls outside the window.

function maxSlidingWindow(nums, k) {
  const deque = []; // indices, values decreasing
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] <= i - k) deque.shift(); // outside the window
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i])
      deque.pop();
    deque.push(i);
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
}

Complexity: Time O(n), Space O(k) (note: shift() is O(n) in JS — use a head pointer for large inputs)