Finding The Max Of Each Continguous Subarray Of A Given Size

May 30, 2024 Post a Comment

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

defdiff_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 windowfor i inrange(win):
        #remove anything that isn't greater than the new itemwhilelen(Q) > 0and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)

    win_maxes.append(arr[Q[0]])

    for i inrange(win, len(arr)):
        #remove indexes (at most 1, really) left of windowwhilelen(Q) > 0and Q[0] <= (i-win):
            Q.popleft()

        #remove anything that isn't greater than the new itemwhilelen(Q) > 0and 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

defcalc(xs, k):
    k_max = []
    result = []

    for ind, val inenumerate(xs):
        # update local maxes (all are active)for i inrange(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:

defnwise(iterable, n):
    ''' Step through the iterable in groups of n '''
    ts = it.tee(iterable, n)
    for c, t inenumerate(ts):
        next(it.islice(t, c, c), None)
    returnzip(*ts)

defmax_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]

Python Manual