Sliding Window Maximum

Hard · Sliding Window

You are given an array of integers and a window size k. Slide a window of length k from the left edge of the array to the right, one step at a time, and record the largest value inside the window at each position. Return the list of these maximum values in the order the windows occur. The array can be large, so recomputing the max from scratch for every window is not fast enough for full credit.

Examples

Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Why:    The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7] and their maxima are 3,3,5,5,6,7.

Input:  nums = [9,11], k = 2
Output: [11]
Why:    There is only one window covering the whole array, whose max is 11.

Input:  nums = [4,-2], k = 1
Output: [4,-2]
Why:    With window size 1 every element is its own window, so the maxima are the elements themselves.

Constraints

1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4, 1 <= k <= nums.length

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Sliding Window Maximum

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Sliding Window Maximum. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.