Finding The Max Of Each Continguous Subarray Of A Given Size

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 doubl

Solution 1:

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.

Solution 2:

What about this approach (which only needs one pass over the data):

Code

def calc(xs, k):
    k_max = []
    result = []

    for ind, val in enumerate(xs):
        # update local maxes (all are active)
        for i in range(len(k_max)):
            if val > k_max[i] :
                k_max[i] = val
        # one new sub-array starts
        k_max.append(val)

        if ind >= (k-1):  # one sub-array ends
            result.append(k_max[0])
            k_max.pop(0)

    return result

t1 = [1, 3, -1, -3, 5, 3, 6, 7]
t2 = [12, 1, 78, 90, 57, 89, 56]
print(calc(t1, 3))
print(calc(t2, 2))

Output

[3, 3, 5, 5, 6, 7]
[12, 78, 90, 90, 89, 89]

Solution 3:

Here's a simple solution using itertools and tee:

def nwise(iterable, n):
    ''' Step through the iterable in groups of n '''
    ts = it.tee(iterable, n)
    for c, t in enumerate(ts):
        next(it.islice(t, c, c), None)
    return zip(*ts)

def max_slide(ns, l):
    return [max(a) for a in nwise(ns, l)]

>>> max_slide([1, 3, -1, -3, 5, 3, 6, 7], 3)
[3, 3, 5, 5, 6, 7]
>>> max_slide([12, 1, 78, 90, 57, 89, 56], 3)
[78, 90, 90, 90, 89]