Why is the deque solution to the "Sliding Window Maximum" problem O(n) instead of O(nk)?

Question

The problem is to find the maximum in each subarray of size k in an array of length n.

The brute force method is O(nk). But using a deque, the solution is supposedly O(n). However I am not convinced that it gets to O(n), in particular because of this while loop:

# Remove all elements smaller than 
# the currently being added element  
# (Remove useless elements) 
while Qi and arr[i] >= arr[Qi[-1]] : 
    Qi.pop()

which is inside of a for loop from k to n. Couldn't this technically run up to k times each loop, giving somewhere between O(n) and O(kn)? Is the worst-case time complexity actually O(kn) even for the deque solution?

Answer 1

You can count the number of comparisons done in the while loop separately in two steps, and then add them together. This will also be the total number of iterations of the while loop, and, since each iteration takes a constant amount of time, it will also be the total running time of the while loop.

True comparisons

If Qi and arr[i] >= arr[Qi[-1]] is true, there will also be a pop operation (since this is in the body of the while loop).

Every element is added to the deque exactly once. Thus you can't have more pop operations than the number of elements, which is O(n).

Thus the total number of these comparisons is also O(n).

False comparisons

Qi and arr[i] >= arr[Qi[-1]] can also be false, but this will only happen once for each time we get to the while loop (since, if it's false, the loop will stop and it will carry on with the subsequent code).

The number of times we get to the while loop is equal to the number of iterations of both for loops, which is O(n).

Thus the total number of these comparisons is also O(n).

Total running time

The rest of the code is also O(n), thus the total running time is O(n+n+n) = O(n).

Answer 2

Let's prove that the extreme worst case n * k operations is not possible (just to get the idea, and the rest in-between-ish can be proven similarly):

How to achieve n * k? At each step, we need to make k "pops" from the deque. So the elements in the deque looks like this (in this illustration, k == 5):

before:

| ,              #
| | | ,          #   (like a heavy bowling ball)
| | | | ,        #  
---------------------------------------------------             
^^^^^^^^^        ^
our deque        new badass element coming *vruuuum*

after

#
#     *bang* (sound of all pins knoked down)
#  
---------------------------------------------------             
^
this new guy totally smashed our deque in 5 operations!

but hey... wait a minute

How did our deque accumulated k elements?

Well, for it to accumulate k elements, it should throw much less in the previous k steps (otherwise the deque would be empty from the start). Crap... no n * k for ya :(

---

This makes a more general statement about the dynamics of our algorithm:

If ith element of the array results in m "pops" from the deque, the previous elements would sure be "lame" enough to even out the "badassness" of the ith element.

Now, if you look not from perspective of a deque but from a perspective of a whole array: each time you're throwing a unique array element. So the number of "pops" should not be greater than the number of elements in array, which is n.

Which makes our complexity O(n).

Answer 3

I don't know the mathematical proof but following thought may help understanding it:

Note that indices of elements are stored in deque but for easy explanation about complexity, I'm talking in terms of elements instead of it's index.

When the new element in the window is not larger than largest element in deque (element at front of the dequeue) but larger than at least the smallest element in deque (element at rear of the deque), then we not only compare the new element with elements of deque (from rear to front) to find the right place, but also discard the elememt from deque who are smaller than the new element.

So don't see above mentioned operation as searching the right place of new element in a sorted deque of length k, instead look it as popping of deque elements smaller than the new element. Those smaller elements were added in deque at some point, the lived there for a while and now they are popped. In the worst case, each element may get this privilege of pushing into and popping from deque (although this is done alongside the operation of searching the first number from rear larger than new element and that causes all confusion).

And as each element can be pushed and popped at most once, hence the complexity is linear.