Problem overview
The method maxSlidingWindow receives an array nums and an integer k. A window of size k starts at the left end of nums and slides right one position at a time until it reaches the right end. At each position the window covers k neighbouring values. The method returns an array with the largest value of each window, from left to right.
For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, there are six windows: [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7]. Their maximums are 3, 3, 5, 5, 6 and 7, so the answer is [3, 3, 5, 5, 6, 7]. In general, an array of n values has n - k + 1 windows.
Approach: a deque of candidates, decreasing from front to back
The brute-force method scans the k values of every window and takes their maximum. That is O(n · k) time, and with n up to 100,000 and k as large as n it is too slow. The lesson asks for O(n).
The key observation: suppose a value a comes before a value b in the array, and a <= b. Then a leaves the window first, so for as long as a is in a window, b is there too and is at least as big. Value a can never be a window's maximum again, and you can forget it.
So keep a list of candidates: indexes of values that can still become a maximum. Every time a new value arrives, remove the candidates at the back that are not bigger than it, then add the new index at the back. What remains is decreasing from front to back, so the front is always the biggest value in the window. When the front index slides out of the window, it is dropped, and the next one takes over.
A list that you take from at both ends is a double-ended queue, or deque. JavaScript has no built-in one, so the lesson uses an array: push and pop work at the back, and a separate position, head, marks the front. Calling shift() to remove the first element would move every other element, while moving head forward costs nothing. The entries before head are simply ignored.
The deque stores indexes, not values. The value is nums[index], and the index also tells you when an entry has left the window.
Here is the state of the deque after each value of the example, with the values shown next to the result so far:
i 0 nums[i] 1 deque indexes [0] values [1] result []
i 1 nums[i] 3 deque indexes [1] values [3] result []
i 2 nums[i] -1 deque indexes [1,2] values [3,-1] result [3]
i 3 nums[i] -3 deque indexes [1,2,3] values [3,-1,-3] result [3,3]
i 4 nums[i] 5 deque indexes [4] values [5] result [3,3,5]
i 5 nums[i] 3 deque indexes [4,5] values [5,3] result [3,3,5,5]
i 6 nums[i] 6 deque indexes [6] values [6] result [3,3,5,5,6]
i 7 nums[i] 7 deque indexes [7] values [7] result [3,3,5,5,6,7]
When the 3 arrives at index 1, the 1 is removed from the back because it is not bigger. The 5 at index 4 removes everything, since it beats all of them. The 3 at index 5 stays behind the 5: it may become the maximum later, once the 5 leaves.
Step by step
- Create
candidates, an emptynumber[]declared withlet. It will hold indexes whose values decrease from front to back. - Declare
headas 0, the position of the deque's front insidecandidates. - Create
result, another emptynumber[], for the maximums. - Loop over every index
i. On each turn the window is thekvalues that end at indexi. - Drop the front if it left the window. The window now starts at
i - k + 1, so a front index ofi - kor less is outside it. Only one index leaves per turn, so oneifis enough. - Pop the weaker candidates from the back with a
whileloop, as long as the deque is not empty and the back value is<= nums[i]. Thehead < candidates.lengthcheck stops the loop from popping entries that already left at the front. - Remove the back with
candidates.pop()inside that loop. - Add
iat the back withpush. Every value left in the deque is bigger thannums[i], so the order stays decreasing. - Record a maximum once the window is full. From
i >= k - 1on, the window holdskvalues, and its maximum isnums[candidates[head]], the front of the deque. - Return
resultafter the loop.
The solution in TypeScript
class Solution {
maxSlidingWindow(nums: number[], k: number): number[] {
let candidates: number[] = [];
let head = 0;
let result: number[] = [];
for (let i = 0; i < nums.length; i++) {
if (head < candidates.length && candidates[head] <= i - k) head++;
while (head < candidates.length && nums[candidates[candidates.length - 1]] <= nums[i]) {
candidates.pop();
}
candidates.push(i);
if (i >= k - 1) result.push(nums[candidates[head]]);
}
return result;
}
}
Details that matter in TypeScript:
- The array as a deque.
candidates.pop()removes the last element andcandidates.push(i)adds one at the end, both in constant time. The front is not removed from the array:headonly moves past it, so the real deque is the part of the array fromheadto the end. - Checking
head < candidates.length. It means "the deque is not empty". Entries beforeheadare no longer part of the deque even though they are still in the array, so testingcandidates.lengthalone would not do. - Annotations are erased. The
number[]types exist only for the compiler. In the JavaScript that runs,candidatesandresultare ordinary arrays. - Comparing with
<=, not<. For equal values, the older one is dropped. That is safe, because the newer one stays in the window longer, and it keeps the deque strictly decreasing. - The array only grows. Entries before
headare never deleted, socandidatescan end up holding up to n indexes in total. That is why the extra space is O(n) and not O(k).
Complexity
Time: O(n). The loop runs n times. Inside it, the if and the push are constant work. The while loop looks like it could be slow, but each index is pushed once and popped at most once over the whole run, so all its iterations add up to at most n. The size of k does not matter.
Space: O(n). The result array has n - k + 1 values. The candidates array is never shortened at the front, so over a whole run it can hold up to n indexes: for example, when nums is decreasing, nothing is ever popped.
Edge cases and common mistakes
- A single value.
[1]withk = 1gives[1]. k = 1. Every window is one value, so the answer isnumsitself.kequal to the length. There is one window, and the answer is a one-value array.[5, 3, 4]withk = 3gives[5].- The maximum slides out. For
[7, 2, 4]andk = 2, the first window gives 7. When the window moves to[2, 4], index 0 is out of range and is dropped from the front, leaving the 4. The answer is[7, 4]. - Equal values.
[4, 4, 4]withk = 2gives[4, 4]. - Storing values instead of indexes. Then you can't tell when the front has left the window.
- Recording a result too early. Before index
k - 1the window has fewer thankvalues, so no maximum is added yet. - Using
shift()to drop the front. It works, but it moves every other element each time, which is slow for large inputs.
Testing
[1, 3, -1, -3, 5, 3, 6, 7],k = 3gives[3, 3, 5, 5, 6, 7].[9, 8, 7, 6],k = 2gives[9, 8, 7].[1, 2, 3, 4],k = 2gives[2, 3, 4].[1, 3, 1, 2, 0, 5],k = 3gives[3, 3, 2, 5].[-7, -8, 7, 5, 7, 1, 6, 0],k = 4gives[7, 7, 7, 7, 7].
