Problem overview
The method maxSlidingWindow receives a vector nums and an integer k. A window of size k starts at the left end of nums and moves right one position at a time until it reaches the right end. The method returns a vector 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, and their maxima are [3, 3, 5, 5, 6, 7]. For nums = [7, 2, 4] and k = 2 the windows are [7, 2] and [2, 4], so the answer is [7, 4]: once the 7 has left, the 4 is the largest value. A vector of length n has n - k + 1 windows.
Approach: keep only the candidates
The simple solution scans all k values of every window, which takes O(n · k) time. With n up to 100,000 and k as large as n, that is too slow. The target is O(n).
The key observation is that many values can never be a window's maximum. Suppose a value x sits to the left of a value y and x <= y. The value x leaves the window first, and as long as x is inside, y is inside too and is at least as big. So x is useless from then on and can be forgotten.
Applying that rule keeps a list of candidates whose values decrease from front to back. The front is the largest value in the window, which is the answer for it. The list changes at both ends: new candidates arrive at the back, after removing the smaller ones there, and the front leaves when it slides out of the window. A deque does both in constant time. It stores indexes rather than values, because an index tells us both the value (nums[index]) and whether the entry has left the window.
Here is the deque at each step of the first example, with k = 3:
| i | nums[i] | indexes in deque | values in deque | window max |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | - |
| 1 | 3 | 1 | 3 | - |
| 2 | -1 | 1, 2 | 3, -1 | 3 |
| 3 | -3 | 1, 2, 3 | 3, -1, -3 | 3 |
| 4 | 5 | 4 | 5 | 5 |
| 5 | 3 | 4, 5 | 5, 3 | 5 |
| 6 | 6 | 6 | 6 | 6 |
| 7 | 7 | 7 | 7 | 7 |
At i = 4, index 1 is outside the window (which now starts at index 2), so it leaves from the front, and then the incoming 5 removes the two smaller candidates at the back. The first two rows have no maximum yet because the window isn't full.
Step by step
- Create
candidates, adeque<int>of indexes whose values decrease from front to back. A deque adds and removes at both ends in constant time:front()andback()read the ends,pop_front()andpop_back()remove them, andpush_backadds at the back. - Create
result, an emptyvector<int>for the maxima. - Loop over every index
i. Each turn,iis the right end of the window, which is thekvalues ending ati. - Drop the front if it left the window. The window starts at
i - k + 1, so an index ofi - kor less is outside it. Indexes are in increasing order, so the oldest is at the front, and at most one index leaves per turn: oneifis enough. - Pop the useless values at the back with a
whileloop that runs while the deque isn't empty andnums[candidates.back()] <= nums[i]. - Remove the back with
pop_back()inside that loop. - Add
iat the back. It is smaller than everything left in the deque, so the values still decrease. - Record the maximum once the window is full. When
i >= k - 1, the window holdskvalues, and its maximum isnums[candidates.front()]. - Return
result.
The solution in C++
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> candidates;
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
if (!candidates.empty() && candidates.front() <= i - k) candidates.pop_front();
while (!candidates.empty() && nums[candidates.back()] <= nums[i]) {
candidates.pop_back();
}
candidates.push_back(i);
if (i >= k - 1) result.push_back(nums[candidates.front()]);
}
return result;
}
};
C++ details worth knowing:
- Test for emptiness before reading.
front()andback()on an empty deque are undefined behaviour. Both conditions put!candidates.empty()first, and&&stops evaluating as soon as it is false. pop_frontandpop_backreturn nothing. Read the element first if you need it. Here the code only needs the indexes to disappear.- Why
<=and not<. Removing equal values is safe: the newer equal value lives at least as long as the older one. It also keeps the deque strictly decreasing, so it never grows with duplicates. For[2, 2, 2]withk = 2the result is[2, 2]. - Signed and unsigned.
nums.size()is unsigned, andiis anint. The comparisoni < nums.size()convertsito unsigned, which is harmless becauseiis never negative.i - kis computed inintand may be negative, which is fine.
Complexity
Time: O(n). Each index is pushed onto the deque once and popped at most once, either from the back by a larger value or from the front by sliding out. The inner while loop looks expensive, but in total it removes at most n entries over the whole run, no matter how big k is.
Space: O(n). The result has n - k + 1 values, and the deque holds at most k indexes.
Edge cases and common mistakes
- One window. When
kequals the length ofnums, the result has a single value. For[5, 1, 4]withk = 3it is[5]. k = 1. Every value is its own window, so the result is a copy ofnums. For[9, 8, 7]it is[9, 8, 7].- Decreasing input. For
[4, 3, 2, 1]withk = 2nothing is ever removed from the back, and the result is[4, 3, 2]: the front leaves by sliding out. - Increasing input. For
[1, 2, 3, 4]withk = 2each new value clears the deque, and the result is[2, 3, 4]. - Storing values instead of indexes. Then there is no way to tell that the front has left the window.
- Recording a maximum too early. Before
ireachesk - 1, the window isn't full. The result would have too many values. - Checking the front only after recording. The front must be dropped before reading the maximum, otherwise an old value can be reported.
Testing
[1, 3, -1, -3, 5, 3, 6, 7],k = 3gives[3, 3, 5, 5, 6, 7].[1],k = 1gives[1].[7, 2, 4],k = 2gives[7, 4].[4, 3, 2, 1],k = 2gives[4, 3, 2].[1, 2, 3, 4],k = 2gives[2, 3, 4].[2, 2, 2],k = 2gives[2, 2].
