CODEWITHSUNDEEP
pythonalgorithmlisttime-complexitydynamic-programming
ComplicatedPhenomenon
ComplicatedPhenomenon

Reputation: 4199

Sliding window maximum in O(n) time

Input:

listi = [9, 7, 8, 4, 6, 1, 3, 2, 5]

Output:

# m=3
listo = [9, 8, 8, 6, 6, 3, 5]

Given a random list composed of n numbers, I need to find all of the sublists of m consequtive elements, choose the largest value from the sublist and put them in a new list.

def convert(listi, m):
    listo = []
    n = len(listi)
    for i in range(n-m+1):
        listo.append(max(listi[i:3+i]))
    return listo

The time complexity for this implementation is O(m\^{(n-m+1)}, which is pretty bad if listi is long, is there a way to implement this in the complexity of O(n)?

Upvotes: 1

Views: 2770

Answers (4)

anh thái huỳnh
anh thái huỳnh

Reputation: 1

Hopefully this is an easy way for you to understand:

from typing import List


def maxSlidingWindow(numList: List[int], windowsSize: int) -> List[int]:
    result = []
    window = numList[:windowsSize - 1]

    for index in range(windowsSize - 1, len(numList)):
        window.pop(0)
        window.append(numList[index])
        result.append(max(window))

    return result


numList = [3, 4, 5, 1, -44, 5, 10, 12, 33, 1]
windowsSize = 3
print(maxSlidingWindow(numList, windowsSize))

result = [5, 5, 1, 5, 10, 12, 33, 33]

Upvotes: 0

user1196549
user1196549

Reputation:

There is a beautiful solution with a running time independent of M.

In the figure below, the first row represents the initial sequence.In the second row, we have the maxima of groups of 1, 2, … M consecutive elements from left to right ("prefix" maxima). In the third row, we have the maxima of groups of 1, 2, … M consecutive elements, from right to left ("suffix" maxima). And in the fourth row, the maxima of elements of the second and third rows.

a   b   c    d    e    f    g    h    i    j    k    l    m    n    o

a   ab  abc  d    de   def  g    gh   ghi  j    jk   jkl  m    mn   mno
        abc  bc   c    def  ef   f    ghi  hi   i    jkl  kl   l    mno  no   o

        abc  bcd  cde  def  efg  fgh  ghi  hij  ijk  jkl  klm  lmn  mno

Note that there are replicated elements in row three, which we needn't compute.

The computation of the second row takes M-1 comparisons per slice of M elements; the second row M-2, and the third M. So ignoring the effect at the ends, we perform slightly less than 3 comparisons per element.

The required storage is an additional array of M elements to temporarily evaluate slices of the third row.

Source: Efficient Dilation, Erosion, Opening and Closing Algorithms, JOSEPH (YOSSI) GIL & RON KIMMEL.

Upvotes: 5

Matt Timmermans
Matt Timmermans

Reputation: 59253

Surprisingly, the easily accessible descriptions of this algorithm are not that easy to understand, so the trick is this:

As you slide a window of length m over your list of length n, you maintain a deque of all the elements in the current window that might, at some point, become the maximum in any window.

An element in the current window might become the maximum if it is greater than all the elements that occur after it in the window. Note that this always includes the last element in the current window.

Since every element in the deque is > all the elements after it, elements in the deque are monotonically decreasing, and the first one is therefore the maximum element in the current window.

As the window slides one position to the right, you can maintain this deque as follows: remove all the elements from the end that are <= the new element. Then, add the new element to the end of the deque. If the element that drops off the front of the window is the first element in the deque, then remove it. Since each element is added and removed at most one time, the total time required to maintain this deque is in O(n).

To make it easy to tell when an element at the front of the deque is falls out of the window, store the elements' indexes in the deque instead of their values.

Here's a reasonably efficient python implementation:

def windowMax(listi, m):
    # the part of this list at positions >= qs is a deque
    # with elements monotonically decreasing.  Each one
    # may be the max in a window at some point
    q = []
    qs = 0

    listo=[]
    for i in range(len(listi)):

        # remove items from the end of the q that are <= the new one
        while len(q) > qs and listi[q[-1]] <= listi[i]:
            del q[-1]

        # add new item
        q.append(i)

        if i >= m-1:
            listo.append(listi[q[qs]])
            # element falls off start of window
            if i-q[qs] >= m-1:
                qs+=1

        # don't waste storage in q. This doesn't change the deque
        if qs > m:
            del q[0:m]
            qs -= m
    return listo

Upvotes: 9

Henry Yik
Henry Yik

Reputation: 22503

I tried timing with zip and it seems the result is 50% faster than your current function - can't really tell the time complexity difference though.

import timeit

setup = """
from random import randint
listi = [randint(1,100) for _ in range(1000)]

def convert(iterable, m):
    t = [iterable[x:] for x in range(m)]
    result = [max(combo) for combo in zip(*t)]
    return result"""

print (min(timeit.Timer('a=listi; convert(a,3)', setup=setup).repeat(7, 1000)))
#0.250054761


setup2 = """
from random import randint
listi = [randint(1,100) for _ in range(1000)]

def convert2(listi, m):
    listo = []
    n = len(listi)
    for i in range(n-m+1):
        listo.append(max(listi[i:3+i]))
    return listo"""

print (min(timeit.Timer('a=listi; convert2(a,3)', setup=setup2).repeat(7, 1000)))
#0.400374625

Upvotes: 1

Related Questions