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.

Answer 4

The complexity of the algorithm is O(nk). On any of the n iterations through array, I may have to compare the new candidate element with up to O(k) elements still in the deque. The while loop inside the for loop gives it away. Consider an array of integers in descending order (of course, the algorithm doesn't have this information). Now I want to find the sliding maximum. Every element that I consider has to be put in the queue, but is incapable of displacing other elements (obviously, because it's smaller). However, I don't know this until I've removed the oldest (and largest) element, and compared the new element to all the remaining ones (ergo, k - 1 comparisons). If I wanted to use a heap as my sliding data structure, I could get the complexity down to O(n log k).

That's the worst case. Assuming the numbers are random, or effectively so within some range, each new element will displace, on average, half the k-size deque. But that's still O(nk).

Answer 5

The time complexity of O(k*n) is deceptive. But if you think about it carefully you will find it is O(n) indeed. I will give my intuition of how the O(n) is derived.

We will think about the time complexity as how many comparisons we need to process all the numbers in the array with dequeue.

Hypothesis：We need just n comparisons.

Proof of the hypothesis:

1. processing the first k numbers

   The first number(with index 0) from the first k numbers will be put into the dequeue without any comparison, since it is the first number to put into the dequeue, now let's consider the ith number where i > 0:

   a. if the ith number from the first k numbers is less than the tail of dequeue, we put it into tail, and stop. This cost us 1 comparison.

   b. if the ith number from the first k numbers is greater than the tail of dequeue, we may need multiple comparisons until we find a numbers that bigger than the ith number or we reached to the head of the dequeue. Let's say we did Ci number of comparisons for ith number. But at the same time it removed Ci number of element from the dequeue. Which mean there is a one to one corresponding between the number of comparison and number of element removed Since the number of elements can be removed while processing the first k elements is at most k. so the number of comparison for processing the first k elements is at most k

2. processing the k+1, k+2...n elements

   Just like the analysis of processing the first k numbers, for every single element j from {k+1, K+2...n} numbers. it will either be less than the tail of dequeue, which cost 1 comparison. or it will do several comparisons until find the right position. but at the same time it removed the same number of elements. Now consider how many elements can be removed by processing {k+1, k+2...n} and {1, 2...k}, it is n which is the length of the array. By applying the one to one corresponding relationship, we know there is n comparisons.

The total time complexity though including the number of comparisons which is n plus the removal and add operations which are both O(n), so the time complexity overall is O(n).

Answer 6

The remove-last operation is a bit tricky.

It seems like taking K times for each looped index but actually all the remove-last operations sums up to less than n, because each element is removed once at maximum.