Sliding Window Maximum

11 Dec 2011

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Input: A long array A[], and a window width w Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: Find a good optimal way to get B[i]

Ok, the most obvious solution is to loop each window, which takes O(nw).

Of course, there is a better solution. Let's observe:

Observation 1

Let's say we have:

5 2 1 3 4 9, and w is 3

The windows are:

[5 2 1] 3 4 9 5 [2 1 3] 4 9 5 2 [1 3 4] 9 5 2 1 [3 4 9]

The first and second windows are highly related. As the window shifts, it removes one element and add another. However, as long as the maximum is not removed, we do not care.

And the solution seems to emerge. We have a pointer on the maximum element in the window. After we shift the window, we do the following:

  • If the maximum is not removed, compare it with the new element and adjust the pointer accordingly. O(1)
  • If the maximum is removed, we have to find the new maximum and update the pointer. O(w) with simple loop, or O(log w) with heap.

And we have to delete element from heap, as the window shifts. So, we need to track indices of elements in a heap. (So complicated)

The best solution we've got so far takes O(n log w). It's not good enough. Let's try to find O(n). The worst case is shown as follows:

6 5 4 3 2 1

We have to update the pointer every time the window shifts.

Basically, we need a data structure that:

  • Get maximum with O(1)
  • Remove element by its index with O(1)
  • Add element with O(1)

… …

Ok, I give up. Let's look at Leetcode.com.

Leetcode.com's solution

It uses double-ended queue. The queue is kept sorted at all time in a very smart way.

The maximum index is in the front, the minimum index is in the back of the queue, and the queue stores indices.

When the window shifts, we:

  1. Remove all elements that is less than the new element from the back.
  2. Remove all elements that are out of the window from the front.
  3. Then add the new element to the back of the queue.
  4. Get the maximum of the current window from the front.

This means that some elements, which are not in the windows, can still be in the queue. But they are not in the front or the back. There are 2 observations here.

Observation 1

We do not remove the element immediately when it is out of the window. We only need remove it when it's in the front.

Observation 2

Let's see this example:

[5 1 3] 4

We don't have to keep 1 because 3 is always a better choice. And when we shift the window, we don't have to keep 3 because 4 is always a better choice.

That's why we just remove all lesser elements from the back of the queue and add the new element at the back.

That is a very very smart trick. Each element is added and removed at most once, and there is no loop over the queue. Therefore, the time complexity is O(n).

That is very very smart!

Give it a kudos