Finding the max of each continguous subarray of a given size
Question: I'm trying to solve the following problem in Python

> Given an array and an integer k, find the maximum for each and every
> contiguous subarray of size k.

The idea is to use a double ended queue. This is my code:

    
    
    def diff_sliding_window(arr, win):
    #     max = -inf
        Q = []
        win_maxes = [] # max of each window
        for i in range(win):
            print(Q)
            while len(Q) > 0 and arr[i] >= arr[len(Q) - 1]:
                # get rid of the index of the smaller element
                Q.pop() # removes last element
            Q.append(i)
    #     print('>>', Q)
    
        for i in range(win, len(arr)):
    #         win_maxes.append(arr[Q[0]])
            print(arr[Q[0]])
            while len(Q) > 0 and Q[0] <= i - win:
                Q.pop()
            while len(Q) > 0 and arr[i] >= arr[len(Q)-1]:
                Q.pop(0)
            Q.append(i)
    #     win_maxes.append(arr[Q[0]])
    
        print(arr[Q[0]])
    

But I can't figure out why for the test cases:

    
    
    t1 = [1, 3, -1, -3, 5, 3, 6, 7]
    t2 = [12, 1, 78, 90, 57, 89, 56]
    

that I'm not getting the correct results.

* * *

**Update** :

I've made the changes that Matt Timmermans suggested, but I'm still not
obtaining the proper output. For `t2`, and `win = 3`

    
    
    78
    90
    90
    89 <--- should be 90
    89
    

Here is my updated code:

    
    
    from collections import deque
    
    def diff_sliding_window(arr, win):
    #     max = -inf
        Q = deque()
        win_maxes = [] # max of each window
        for i in range(win):
    #         print(Q)
            while len(Q) > 0 and arr[i] >= arr[Q[len(Q)-1]]:
                # get rid of the index of the smaller element
                Q.pop() # removes last element
            Q.append(i)
    #     print('>>', Q)
    
        for i in range(win, len(arr)):
    #         win_maxes.append(arr[Q[0]])
            print(arr[Q[0]])
            while len(Q) > 0 and Q[0] <= i - win:
                Q.pop()
            while len(Q) > 0 and arr[i] >= arr[Q[len(Q)-1]]:
                Q.popleft()
            Q.append(i)
    
    
        print(arr[Q[0]])
    


Answer: It looks like you are trying to implement the O(n) algorithm for this problem,
which would be better than the other two answers here at this time.

But, your implementation is incorrect. Where you say `arr[i] >=
arr[len(Q)-1]`, you _should_ say `arr[i] >= arr[Q[len(Q)-1]]` or `arr[i] >=
arr[Q[-1]]`. You also swapped the `pop` and `pop(0)` cases in the second loop.
It looks like it will be correct after you fix those.

Also, though, your algorithm is not O(n), because you using `Q.pop(0)`, which
takes O(k) time. Your total running time is therefore O(kn) instead. Using a
deque for `Q` will fix this.

Here it is all fixed, with some comments to show how it works:

    
    
    from collections import deque
    
    def diff_sliding_window(arr, win):
    
        if win > len(arr):
            return []
    
        win_maxes = [] # max of each window
    
        #Q contains indexes of items in the window that are greater than
        #all items to the right of them.  This always includes the last item
        #in the window
        Q = deque()
    
        #fill Q for initial window
        for i in range(win):
            #remove anything that isn't greater than the new item
            while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
                Q.pop()
            Q.append(i)
    
        win_maxes.append(arr[Q[0]])
    
        for i in range(win, len(arr)):
            #remove indexes (at most 1, really) left of window
            while len(Q) > 0 and Q[0] <= (i-win):
                Q.popleft()
    
            #remove anything that isn't greater than the new item
            while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
                Q.pop()
            Q.append(i)
            win_maxes.append(arr[Q[0]])
    
        return win_maxes
    

try it: <https://ideone.com/kQ1qsQ>

Proof that this is O(N): Each iteration of the inner loops removes an item
from Q. Since there are only `len(arr)` added to Q in total, there can be at
most `len(arr)` _total_ iterations of the inner loops.

