239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:

You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:

Could you solve it in linear time?

This problem is more a quiz-like problem that tagged with heap while no one actually uses the heap in the general idea to solve the problem. I first present the queue solution I come up with, which is maybe the “regular solution”, and another amazing algorithm without queue.

Regular Solution with Queue

My accepted code can be found here

The basic idea comes from we need to preserve as much information as possible for the elements when the window is sliding. A naive approach is to record every element in the window, at the cost of the maximum searching time being linear to the size of the window (O(k)), which is not good.

And the observation is that if we scan the array from the beginning to the end, whenever a element joins the window, the smaller elements before it in index are no longer needed, since we would never select those element in the future due to the present of a larger element, we can discard them all.

How can we do that? We maintain a sorted queue to record needed elements in the window, and each time a new element come in, we discard all elements that’s smaller than the current one from the tail.

Additionally, we need to kick the element that’s no longer in the window out of the queue, maintaining the queue as above give the queue another nice property, it’s not only sorted by the element but also the index of element, so all we need to do is to check whether the head of the queue is out of range everytime we move a window.

And finally, the algorithm:

SlidingWindowMaximum(nums: int[], k: int): int[]:
    let result = empty integer array
        queue = empty integer queue
    for i = 0 until k - 1:
        PushQueue(queue, i, nums[i])
    for i = k - 1 until length(nums):
        KickOutOfRange(queue, i, k)
        PushQueue(queue, i, nums[i])
        append(result, head(queue).element)

PushQueue(queue: Queue, idx: int, elem: int):
    for queue is not empty and tail(queue).element <= elem:
        pop_tail(queue)
    push_tail(queue, {index: idx, element: elem})

KickOutOfRange(queue: Queue, idx: int, k: int):
    if head(queue).index <= idx - k:
        pop_head(queue)

The time complexity is O(n) since each element is at most pushed and popped once, extra space is O(k).

Another Clean Solution

This solution comes from the discussion of this problem

This solution is too clean to understand easily, it has the following step:

  1. partition the input array every k elements, such as for input = [1,3,-1,-3,5,3,6,7], k = 3, the partition result is [1,3,-1 | -3,5,3 | 6,7]
  2. for each partition of the array, calculate the accumulate maximum from left to right, obtaining a new array with the same length of the input, e.g. the accumulate maximum of [1,3,2,5,4] is [1,3,3,5,5], result being left_max
  3. for each partition, calculate the accumulate maximum again, but from right to left, result being right_max.
  4. result[i] = max(right_max[i], left_max[i + k - 1])

I don’t actually know how this genius came up with the solution, but here are some observations:

  1. right_max[i] and left_max[i + k - 1] must be inside the window [i, i + k - 1]
  2. most of the time, the input partition method split the window to the left side and right side, and right_max[i] is the maximum of the left part, left_max[i + k - 1] is the maximum of the right part
  3. the maximum of the maximum of left and right part is the maximum of the whole window

The time and space complexity are both O(n), but the solution is a lot more creative than the one using queue.