Maximum of all subarrays of size k (sliding window maximum)

Medium

Problem

For every contiguous window of size k, return its maximum. Aim for O(n) overall.

Example 1

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

Also asked as: Maximum of all subarrays of size k

Test cases

Case 1

Input:    [1,3,-1,-3,5,3,6,7], 3
Expected: [3,3,5,5,6,7]

Case 2

Input:    [1], 1
Expected: [1]

Case 3

Input:    [9,8,7,6], 2
Expected: [9,8,7]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Monotonic decreasing deque

Time O(n)Space O(k)

Keep indices whose values are decreasing. Pop smaller values from the back on insert; pop the front when it leaves the window. The front is the current window max.

function maxSlidingWindow(a, k) {
const dq = [], res = [];
for (let i = 0; i < a.length; i++) {
while (dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop();
dq.push(i);
if (dq[0] <= i - k) dq.shift();
if (i >= k - 1) res.push(a[dq[0]]);
}
return res;
}

A max-heap of (value, index) also works in O(n log k) — pop stale indices lazily.