Sliding Window Maximum

The problem

Array nums and integer k. Return an array of the maximums of each contiguous window of size k.

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

Brute force

For each window start, scan k elements. O(n·k).

function maxSlidingWindowBrute(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let m = -Infinity;
    for (let j = i; j < i + k; j++) m = Math.max(m, nums[j]);
    res.push(m);
  }
  return res;
}

Optimal: monotonic deque

Deque stores indices in decreasing order of values. Front is always the max of the current window.

For each index i:

1. Pop back while nums[back] ≤ nums[i] (they can never be max after i).
2. Push i.
3. Pop front if front ≤ i - k (out of window).
4. If i ≥ k - 1, record nums[front].

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = []; // indices, values decreasing
  const res: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
      dq.pop();
    }
    dq.push(i);

    if (dq[0] <= i - k) dq.shift();

    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}

Time	O(n) amortized — each index pushed/popped once
Space	O(k)

Note: shift() on JS array is O(n); for purity use a head index or circular buffer. Interview-scale usually OK if you mention it.

Heap approach

Max-heap of (value, index), lazy-delete outdated indices. O(n log n). Deque is cleaner.

Edge cases

• k = 1 → copy of array
• k = n → single global max
• Strictly decreasing / increasing sequences
• Negatives

Common bugs

• Storing values instead of indices (can’t expire by position)
• Using < instead of ≤ (duplicates)
• Forgetting to wait until window is full before recording

Interview delivery

1. Brute O(nk).
2. Monotonic deque of indices.
3. Dry-run one window slide.
4. O(n)/O(k).
5. Mention heap alternative.

Related

• Longest Substring Without Repeating
• Minimum Window Substring
• Daily Temperatures
• Min Stack

Deque contents meaning

Indices increase left→right in the deque structure, but values are decreasing. Front = current max. When a new value arrives larger than the back, pop backs — those indices leave the window later and can never beat the new value as max.

Why store indices not values

You need to drop entries that slid out of the window (index <= i-k). Values alone don’t tell you their positions when duplicates exist.

shift() cost note

JS array shift is O(n). For an O(n) algorithm strictly, use a head pointer:

// deque as array + head index instead of shift
let head = 0;
// pop front: head++
// empty when head >= dq.length; occasionally compact

Saying this earns engineering points without rewriting the whole solution mid-interview.

Further reading

• LeetCode 239 — Sliding Window Maximum
• Monotone queue