hard

Sliding Window Maximum

Find the maximum value inside every fixed-size window as it slides across an array.

1. Define the problem

Sliding Window Maximum

Given an array nums and a window size k , return the maximum in every contiguous window of size k as it slides from left to right. Maintain a decreasing deque of indices so the front is always the current max.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -104 ≤ numsi ≤ 104
  • 1 ≤ k ≤ nums.length

Example

Inputnums = [1,3,-1,-3,5,3,6,7], k = 3
Output[3,3,5,5,6,7]

Explanation Each position records the max of the length-3 window ending there once the window is full.

2. Visualize the solution

Deque keeps the max at the front

Deque keeps the max at the front
StatusFull

First full window [1,3,-1]; deque front is 3 → result [3].

What happens in this step

window = [0, 2]  values [1, 3, -1]

deque (index:value): push 0(1) → pop 0(1) since 1<=3, push 1(3) → push 2(-1), no pop (3<=-1 is false)
deque = [1(3), 2(-1)]

front value = 3 → max = 3. result = [3]
Step 1 of 5

Steps to visualize

  1. Slide a fixed window of size k from left to right across the array.
  2. Maintain a decreasing deque of indices so the front is always the window max.
  3. Drop indices that fall out of the left edge of the window.
  4. Pop smaller values from the back before pushing the new right index.
  5. Once the window is full, append the deque-front value to the result each step.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Deque keeps the max at the front
StatusFull

First full window [1,3,-1]; deque front is 3 → result [3].

What happens in this step

window = [0, 2]  values [1, 3, -1]

deque (index:value): push 0(1) → pop 0(1) since 1<=3, push 1(3) → push 2(-1), no pop (3<=-1 is false)
deque = [1(3), 2(-1)]

front value = 3 → max = 3. result = [3]
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function maxSlidingWindow(nums, k) {
  if (nums.length === 0 || k <= 0) return [];

  const deque = [];
  const result = [];

  for (let right = 0; right < nums.length; right++) {
    while (deque.length > 0 && deque[0] <= right - k) {
      deque.shift();
    }

    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[right]) {
      deque.pop();
    }

    deque.push(right);

    if (right >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}
Time
O(n)
Space
O(k)
5. Test cases

Test cases

InputExpectedCovers
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]Docstring example
nums = [], k = 3[]Empty array
nums = [4,2,9,1], k = 1[4,2,9,1]k = 1 returns the array unchanged
nums = [4,2,9,1], k = 4[9]k equals array length
nums = [5], k = 1[5]Single element array
nums = [9,8,7,6,5], k = 2[9,8,7,6]Strictly decreasing array
nums = [1,2,3,4,5], k = 2[2,3,4,5]Strictly increasing array
nums = [7,7,7,7], k = 2[7,7,7]All identical values
nums = [9,11,-3,2,4,6,-8,0,15,3,-2,5,12], k = 4[11,11,6,6,6,15,15,15,15,12]Larger hand-verified case
nums = [-4,-2,-9,-1,-5], k = 2[-2,-2,-1,-1]Negative numbers only

Keep reading

TopicDescription
Sliding WindowSolve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides.
Maximum Average Subarray IFind the contiguous subarray of a fixed length with the largest average.
Longest Substring Without Repeating CharactersFind the length of the longest run of characters in a string with no repeats.
Permutation in StringCheck whether one string contains a rearrangement of another string as a substring.
Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least a target value.
Longest Repeating Character ReplacementFind the longest substring you can turn into one repeated letter with a limited number of swaps.