Problem overview
The method MaxSlidingWindow receives an int[] named nums and an int named k. A window of k neighbouring values starts at the left end and moves right one position at a time. The method returns an int[] with the largest value of each window, from left to right. An array of length n has n - k + 1 windows, so the result has that length.
For nums = {1, 3, -1, -3, 5, 3, 6, 7} and k = 3 the windows are {1, 3, -1}, {3, -1, -3}, {-1, -3, 5}, {-3, 5, 3}, {5, 3, 6} and {3, 6, 7}, and the result is {3, 3, 5, 5, 6, 7}. For {7, 2, 4} and k = 2 it is {7, 4}: once the 7 has left the window, 4 is the largest value.
Approach: keep only the values that can still win
Finding the maximum of every window from scratch takes O(n * k) time, too slow when both are in the tens of thousands. The faster idea is to keep a small list of candidates, the values that can still become the maximum of some window.
Suppose a new value nums[i] arrives, and an older value in the candidates is not bigger than it. That older value will leave the window before nums[i] does, so as long as it stays in the window, nums[i] is there too and is at least as big. It can never be a maximum again, so we throw it away. After this clean-up, the candidates are in decreasing order of value from front to back, and the front is the maximum of the window.
The candidates are stored as indexes, not values. The index tells us when an entry has slid out of the window: the window ending at i starts at i - k + 1, so the front leaves when its index is i - k or less. This structure is a monotonic deque: values leave at the back (when a bigger one arrives) and at the front (when they slide out).
The trace for the first example, showing the deque as index(value), front first:
i=0 nums[i]=1 deque=[0(1)] max=-
i=1 nums[i]=3 deque=[1(3)] max=-
i=2 nums[i]=-1 deque=[1(3) 2(-1)] max=3
i=3 nums[i]=-3 deque=[1(3) 2(-1) 3(-3)] max=3
i=4 nums[i]=5 deque=[4(5)] max=5
i=5 nums[i]=3 deque=[4(5) 5(3)] max=5
i=6 nums[i]=6 deque=[6(6)] max=6
i=7 nums[i]=7 deque=[7(7)] max=7
When 5 arrives at i=4, it removes everything smaller before it, and the old front (index 1) has just slid out of the window. When 6 and 7 arrive, they clear the deque completely.
Step by step
- Create
candidates, aList<int>that plays the deque. It holds indexes ofnums. - Create
head, anintat 0, marking where the deque's front is inside the list. Removing the first element of aListmoves all the others, which costs O(n). Movingheadforward costs O(1), and the entries before it are simply ignored. - Create
result, anint[]of sizenums.Length - k + 1. - Loop over every index
i. Hereiis the right end of the window. - Drop the front if it left the window. If the deque isn't empty and
candidates[head] <= i - k, dohead++. Indexes come in increasing order, and only one index can leave per turn, so one check is enough. - Drop the weaker values at the back. A
whileloop runs while the deque isn't empty andnums[candidates[candidates.Count - 1]] <= nums[i]. Checkinghead < candidates.Countfirst keeps the loop from touching entries that already left at the front. - Remove the back with
candidates.RemoveAt(candidates.Count - 1). At the last index nothing else has to move. - Add
iat the back withcandidates.Add(i). Every value left in the deque is bigger thannums[i], so the order stays decreasing. - Store the maximum when the window is full. If
i >= k - 1, the front is the window's maximum:result[i - k + 1] = nums[candidates[head]]. - Return
result.
The solution in C#
class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
List<int> candidates = new List<int>();
int head = 0;
int[] result = new int[nums.Length - k + 1];
for (int i = 0; i < nums.Length; i++) {
if (head < candidates.Count && candidates[head] <= i - k) head++;
while (head < candidates.Count && nums[candidates[candidates.Count - 1]] <= nums[i]) {
candidates.RemoveAt(candidates.Count - 1);
}
candidates.Add(i);
if (i >= k - 1) result[i - k + 1] = nums[candidates[head]];
}
return result;
}
}
The C# details worth knowing:
- A
Listas a deque. The lesson works on aList<int>:AddandRemoveAtat the last index are O(1), and the separateheadstands in for removing at the front. ALinkedList<int>would work as a deque too (AddLast,RemoveLast,RemoveFirst), at the price of allocating a node for every entry. Countfor lists,Lengthfor arrays.candidates.Countis the number of items in the list,nums.Lengththe length of the array. Mixing them up is a compile error.- Entries before
headstay in the list. They are never read again, which is why everyhead < candidates.Countcheck matters: without it, an emptied deque would still look non-empty to thewhileloop. - Index expressions nest.
nums[candidates[candidates.Count - 1]]reads the last index in the list, then the value at that index innums. <=, not<. Removing equal values at the back is safe, and it keeps the deque short.List<T>lives inSystem.Collections.Generic. In a file of your own, addusing System.Collections.Generic;.
Complexity
Time: O(n). Each index is added to the deque once and removed at most once, either at the back by the while loop or at the front by head++. So the total work of all the inner steps is bounded by n, however large k is.
Space: O(n). The result has n - k + 1 values, and the list can hold up to n indexes, because entries before head aren't deleted. A circular buffer or a real deque could keep the working storage down to k entries.
Edge cases and common mistakes
k = 1. Every window is a single value, so the result equalsnums:{3, 1, 2}gives{3, 1, 2}.k = nums.Length. There is one window.{9, 8, 7}withk = 3gives{9}.- Increasing input.
{1, 2, 3, 4}withk = 2gives{2, 3, 4}: each new value clears the deque. - Decreasing input.
{4, 3, 2, 1}withk = 2gives{4, 3, 2}: the deque keeps growing until the front slides out. - Equal values.
{5, 5, 5, 5}withk = 3gives{5, 5}. - All negative.
{-5, -2, -9, -1}withk = 2gives{-2, -2, -1}. Starting the maximum at 0 would be wrong here. - Storing values instead of indexes. Without indexes, there is no way to tell when the front has left the window.
- Recomputing each window's maximum with a loop, or with LINQ's
Max(). That is O(n * k) and times out on the largest inputs. - Writing to
resulttoo early. Beforeireachesk - 1the window isn't full yet, andi - k + 1would be negative.
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}.{-5, -2, -9, -1},k = 2gives{-2, -2, -1}.
