Sliding Window Maximum

Hard

The problem

Given a list of numbers and a window size k, slide a window of k numbers from the left end to the right end of the list, one step at a time. Return a list with the biggest number inside the window at each step.

Example 1
Input: nums = [4, 2, 12, 3, 8, 1], k = 3
Output: [12, 12, 12, 8]
The windows are [4,2,12], [2,12,3], [12,3,8] and [3,8,1]. Their biggest numbers are 12, 12, 12 and 8.
Example 2
Input: nums = [5], k = 1
Output: [5]
One window with one number.

Limits

1 ≤ nums.length ≤ 100,000
1 ≤ k ≤ nums.length
-10,000 ≤ nums[i] ≤ 10,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

When a new number arrives, which numbers in the window can never be the maximum again?

The idea

Keep a deque of indices with decreasing values: pop from the back while smaller than the new value, pop from the front when it leaves the window. The front is the max.

Target: O(n) time, O(k) space

Go function shape

func maxSlidingWindow(nums []int, k int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MaxSlidingWindow: keep a deque of indexes whose values decrease from front to back.
// A smaller value behind a bigger newcomer can never be the maximum again, so it is dropped.
func MaxSlidingWindow(nums []int, k int) []int {
	var dq, out []int
	for i, v := range nums {
		for len(dq) > 0 && nums[dq[len(dq)-1]] <= v {
			dq = dq[:len(dq)-1] // drop smaller values from the back
		}
		dq = append(dq, i)
		if dq[0] <= i-k {
			dq = dq[1:] // the front index slid out of the window
		}
		if i >= k-1 {
			out = append(out, nums[dq[0]])
		}
	}
	return out
}

Read the lesson: Sliding Window