Problem overview
The function maxSlidingWindow receives a slice 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 it covers k neighbouring values. The function returns a slice with the largest value of each window, from left to right.
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 [1] and k = 1 the only window holds the only value, so the result is [1]. For [7, 2, 4] and k = 2 the windows are [7 2] and [2 4], and the result is [7 4]: once 7 has left the window, 4 is the largest.
A slice of n values has n - k + 1 windows, so the result has that many entries. The lesson asks for O(n) time and O(n) extra space.
Approach: keep only the candidates
Scanning each window for its largest value takes O(k) per window, O(n * k) overall, which is too slow when both are large. We need the maximum without looking at the whole window each time.
The idea is to keep a list of the indexes of values that can still become a window's maximum. Call it the deque. Two rules keep it small and useful:
- Drop a value that is outdone. When a new value
nums[i]arrives, any value before it that is not bigger will leave the window earlier thannums[i], whilenums[i]is at least as big. It can never be a maximum again, so it is removed from the back of the deque. - Drop an index that left the window. The deque holds indexes, not values, so we can tell when the front has slid out of the window.
After these two steps, the values in the deque decrease from front to back, and the front is the largest value of the current window. Reading the maximum is O(1). Each index enters the deque once and leaves it at most once, so all the work adds up to O(n) however large k is.
The deque for the first example, after each value is processed, shown as indexes:
i = 0 nums[i] = 1 deque indexes [0]
i = 1 nums[i] = 3 deque indexes [1]
i = 2 nums[i] = -1 deque indexes [1 2]
i = 3 nums[i] = -3 deque indexes [1 2 3]
i = 4 nums[i] = 5 deque indexes [4]
i = 5 nums[i] = 3 deque indexes [4 5]
i = 6 nums[i] = 6 deque indexes [6]
i = 7 nums[i] = 7 deque indexes [7]
At i = 1, the 3 removes the 1 from the back. At i = 3 the deque holds the indexes 1, 2 and 3, the values 3, -1 and -3: decreasing, with the window's maximum 3 at the front. At i = 4, index 1 has left the window and the 5 is bigger than everything in the deque, so it removes them all and stands alone. At i = 5 the 3 is smaller than 5, so it stays behind it as a candidate for later.
Step by step
- Create the deque. Go has no deque type, so
candidates := []int{}is a slice. Appending and cutting off the last element work at the back, and a separate integer marks the front. - Declare
headas 0: the position of the deque's front incandidates. Movingheadforward costs O(1), and the entries before it are simply ignored. - Create
result, an empty[]int, for the maxima. - Visit every value with a
forloop onifrom 0 tolen(nums)-1. Each turn,iis the right end of the window: thekvalues that end ati. - Drop the front if it left the window. The window starts at
i - k + 1, so an index ofi - kor less is outside. If the deque is not empty (head < len(candidates)) andcandidates[head] <= i-k, dohead++. Indexes come in increasing order, so the oldest is at the front and only one index can leave per turn; one check is enough. - Drop the outdone values from the back. A
forloop with only a condition runs while the deque is not empty and the value at its back,nums[candidates[len(candidates)-1]], is<= nums[i]. - Remove the back with
candidates = candidates[:len(candidates)-1], the slice without its last element. - Add
iat the back withappend, assigning the result back. The valuenums[i]is now smaller than everything before it in the deque, so the values still decrease. It may become a maximum later, once the bigger values ahead of it leave. - Record the maximum when the window is full. For
i >= k-1, appendnums[candidates[head]]toresult. Before that, the window holds fewer thankvalues and isn't one of the problem's windows yet. - Return
resultafter the loop.
The solution in Go
func maxSlidingWindow(nums []int, k int) []int {
candidates := []int{}
head := 0
result := []int{}
for i := 0; i < len(nums); i++ {
if head < len(candidates) && candidates[head] <= i-k {
head++
}
for head < len(candidates) && nums[candidates[len(candidates)-1]] <= nums[i] {
candidates = candidates[:len(candidates)-1]
}
candidates = append(candidates, i)
if i >= k-1 {
result = append(result, nums[candidates[head]])
}
}
return result
}
Go details worth knowing
- A slice as a deque.
candidates[:len(candidates)-1]shortens the slice by one at the back without copying: the new slice shares the same backing array. A laterappendoverwrites the removed slot, which is what we want here. - Assign the result of
append.appendmay need a bigger backing array and returns the slice to use, socandidates = append(candidates, i)must assign back. The same goes forresult. - Why
headand notcandidates[1:]. Cutting the front withcandidates = candidates[1:]also works in Go, but a counter is easy to reason about. Entries beforeheadare never read again. - The
head < len(candidates)check in the inner loop. It stops the loop from removing entries that already left at the front, and from indexing an empty slice. Go checks bounds at run time, and an index out of range panics. []int{}versusnil.result := []int{}is an empty, non-nil slice. Sincenumshas at least one value, the result always has at least one entry.- Short-circuit
&&. Go evaluates the left side first and skips the right side when it is false, socandidates[head]is only read when the deque is not empty.
Complexity
Time: O(n). The outer loop runs n times. The inner loop and the front check look like extra work, but every index is appended once and removed once, either from the back by the inner loop or from the front by head++. So all the removals together are at most n.
Space: O(n). The candidates slice can hold up to n indexes (it does when the values decrease, such as [4, 3, 2, 1], because nothing is ever outdone), and result holds n - k + 1 values.
Edge cases and common mistakes
k = 1. Every window is a single value, so the result isnumsitself.k = len(nums). There is one window, and the result has one entry.[9, 8, 7]withk = 3gives[9].- Equal values. The inner loop uses
<=, so an equal value at the back is removed in favour of the newer one, which stays in the window longer.[5, 5, 5]withk = 2gives[5 5]and the deque never holds more than one index. - Negative numbers. Nothing special happens.
[-5, -3, -4]withk = 2gives[-3 -3]. - Storing values instead of indexes. Then there is no way to tell when the front has left the window.
- Recording a maximum too early. Writing to
resultbeforei >= k-1adds results for windows that are shorter thank. - Using
<instead of<=when dropping from the back. The result stays correct, but equal values pile up in the deque.
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](decreasing values: the deque keeps everything).[1, 2, 3, 4],k = 2gives[2 3 4](increasing values: the deque keeps one index).[5, 5, 5],k = 2gives[5 5].
