Maximum of all subarrays of size k (sliding window maximum)
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]
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.