Problem: Given an array of numbers, find the min/max of a fixed-size sliding window over each index in the array
Deque based solution for sliding window max (min is analogous):
- Remove the element outside the sliding window from the back of the queue.
- While the current element is greater than the front of the queue, remove the element at the front of the queue.
- Insert the current element into the front of the queue.
- The element at the back of the queue is the current sliding window maximum.
To prove that it works, we need to prove that at every iteration, the element at the back of the queue is always the biggest in the sliding window.
To show this, we need the fact that the queue is always sorted with the element at the back being the biggest and the element at the front being the smallest. To see this, simply notice that this property holds at the start, and is maintained at each iteration where a new element is only added to the queue when all the elements smaller than it have been removed.
Next we need to show that all the elements inside the queue are inside the sliding window. Now notice that the queue is not only ordered from biggest to smallest but also from oldest to newest. When an element is added onto the queue, it is either popped from the front or back. Before it is popped, new elements may be added in front of it, but never behind it. This therefore means that an older element can never have a newer element behind it. Therefore the queue is sorted with the oldest at the back and newest at the front. Therefore, when removing outdated elements, we can look from back to front of queue.
Now to prove that it’s O(n). Notice that each element is pushed and popped exactly once – we only ever push the current element onto the front of the queue, and since each element is only on the queue once, it can only be popped off the queue once.
Next we consider the number of comparisons. At each iteration we keep comparing the current element to the front of the queue until it’s no longer greater than the front of the queue. Every time it’s greater than the front of the queue there is a pop, and when it’s no longer greater than the front of the queue we stop comparing and push it to the front of the queue. Therefore the number of comparisons is just one more than the number of pops from the front of the queue plus one. So it is also O(n).
At each iteration we also check if the back of the queue is outside the sliding window, which is a single operation so that is also O(n).