Sliding Window Maximum

Try It Yourself

Use the editor below to return the maximum for every window of size k. Store useful indices in decreasing value order so the front always identifies the maximum.

Submit your implementation when it passes the examples. Remove indices that leave the window and values that can no longer become a maximum.

Sliding Window Maximum

hardDeque · Sliding Window · Monotonic Queue40 minLC 239

Problem

Given an integer array and a window size k, return the maximum value in every contiguous window of size k.

Process the array efficiently without scanning every window from scratch.

Example 1:

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

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

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints

1 ≤ k ≤ nums.length ≤ 100,000
-10,000 ≤ nums[i] ≤ 10,000

0 attempts

Solution

Before adding an index, remove smaller or equal values from the back because the new value will outlast them. Remove the front index when it falls outside the current window.

Once a full window exists, the value at the front index is its maximum.

function maxSlidingWindow(nums, k) {
  const entries = {};
  let front = 0;
  let back = 0;
  const result = [];

  for (let index = 0; index < nums.length; index++) {
    while (front < back && entries[front] <= index - k) {
      delete entries[front];
      front++;
    }

    while (
      front < back &&
      nums[entries[back - 1]] <= nums[index]
    ) {
      back--;
      delete entries[back];
    }

    entries[back] = index;
    back++;

    if (index >= k - 1) {
      result.push(nums[entries[front]]);
    }
  }

  return result;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Each index enters and leaves the deque at most once.
Auxiliary space	`O(k)`	The deque stores only useful indices from the current window.