01. Sliding Window Maximum

Difficulty:HardPattern:Monotonic DequeTime:O(n)Space:O(k)

You are given an array of integers nums, and a sliding window of size k moving from left to right. Return the max sliding window values.

How It Works & Algorithmic Design

Solves using Monotonic Decreasing Double-Ended Queue (Deque):

Deque Invariant: Maintain index values in deque such that elements nums[deque[i]] are strictly decreasing.
Window Processing (For index $i$ from $0$ to $n-1$):
- Remove Out-of-Bound: If deque[0] <= i - k, pop front.
- Maintain Decreasing Order: While nums[i] >= nums[deque[last]], pop back.
- Push: deque.push(i).
- Collect Max: If $i \ge k - 1$, push nums[deque[0]] to result.

Why This Approach Works Best

Maintains sliding window maximums in linear $O(n)$ time using $O(k)$ space without $O(n \log k)$ heap delays.

Example Walkthrough

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Sliding window length 3.

Window Maxes: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7

Sub-array maximums.

Output: [3, 3, 5, 5, 6, 7]

Result array.

Answer: Sliding Window Maximum Monotonic Deque implementation

function maxSlidingWindow(nums, k) {
  const res = [];
  const deque = []; // Stores indices
  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] <= i - k) deque.shift();
    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;
}

💡 Store indices in double-ended queue keeping corresponding values strictly decreasing.

Key Takeaways

Deque maintains element indices in strictly decreasing value order.
Front of deque always holds current window maximum.
Linear time complexity $O(n)$ as every index gets pushed and popped at most once.