Finding the max of each continguous subarray of a given size
<p>I'm trying to solve the following problem in Python</p>

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

<p>The idea is to use a double ended queue. This is my code:</p>

<pre><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) &gt; 0 and arr[i] &gt;= arr[len(Q) - 1]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('&gt;&gt;', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) &gt; 0 and Q[0] &lt;= i - win:
            Q.pop()
        while len(Q) &gt; 0 and arr[i] &gt;= arr[len(Q)-1]:
            Q.pop(0)
        Q.append(i)
#     win_maxes.append(arr[Q[0]])

    print(arr[Q[0]])
</code></pre>

<p>But I can't figure out why for the test cases:</p>

<pre><code>t1 = [1, 3, -1, -3, 5, 3, 6, 7]
t2 = [12, 1, 78, 90, 57, 89, 56]
</code></pre>

<p>that I'm not getting the correct results.</p>

<hr>

<p><strong>Update</strong>:</p>

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

<pre><code>78
90
90
89 &lt;--- should be 90
89
</code></pre>

<p>Here is my updated code:</p>

<pre><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) &gt; 0 and arr[i] &gt;= arr[Q[len(Q)-1]]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('&gt;&gt;', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) &gt; 0 and Q[0] &lt;= i - win:
            Q.pop()
        while len(Q) &gt; 0 and arr[i] &gt;= arr[Q[len(Q)-1]]:
            Q.popleft()
        Q.append(i)


    print(arr[Q[0]])
</code></pre>

<p>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.</p>

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

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

<p>Here it is all fixed, with some comments to show how it works:</p>

<pre><code>from collections import deque

def diff_sliding_window(arr, win):

    if win &gt; 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) &gt; 0 and arr[i] &gt;= 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) &gt; 0 and Q[0] &lt;= (i-win):
            Q.popleft()

        #remove anything that isn't greater than the new item
        while len(Q) &gt; 0 and arr[i] &gt;= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
        win_maxes.append(arr[Q[0]])

    return win_maxes
</code></pre>

<p>try it: <a href="https://ideone.com/kQ1qsQ" rel="nofollow">https://ideone.com/kQ1qsQ</a></p>

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

python algorithm data-structures queue