AlgoViz
HomeStack

Sliding Window Maximum

Hard

A deque of useful indices

Problem

Return the maximum of each sliding window of size k as it moves across the array.

In simple words

Keep a deque of useful indices in decreasing order; its front is always the current window's max.

The idea

Keep a deque of indices whose values decrease from front to back: the front is always the window's maximum. Drop indices that have left the window from the front and pop smaller values from the back before pushing, since a smaller earlier value can never be the maximum again.

The trick

  • Front holds the current maximum; back is where you push.
  • Evict from the front when the index falls out of the window.
  • Each index enters and leaves once — O(n) overall.
1
3
-1
-3
5
3
6
7
0
1
2
3
4
5
6
7
k3

Step 1 of 8. Brute force: re-scan every window of size 3 for its max. Values: 1, 3, -1, -3, 5, 3, 6, 7. k 3.

1/8
Brute force
timeO(n·k)spaceO(1)

Re-scan each window.

1for (let i = 0; i + k <= n; i++) {2  let mx = -Infinity;3  for (let j = i; j < i + k; j++) mx = Math.max(mx, nums[j]);4  res.push(mx);5}

Input

array
[1, 3, -1, -3, 5, 3, 6, 7]

Memory

k
3

Output

maxes
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output:
[3, 3, 5, 5, 6, 7]
Explanation:
The max of each length-3 window.

Example 2

Input:
nums = [1, -1], k = 1
Output:
[1, -1]
Explanation:
Each single element is its own max.

Example 3

Input:
nums = [9, 8, 7], k = 2
Output:
[9, 8]
Explanation:
Window maxes are 9 then 8.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.