Algorithms: Maximum Sliding Window

09/18/2017

Tags: sliding window algorithms deque

The sliding window problem seeks to evaluate properties about every possible subarray without introducing a look-back penalty. In particular, the Maximum Sliding Window problem tries to find the maximum element in every contiguous fixed-length subarray.

Consider an array of integers $A$ length $n$ and integer $k \le n$. For each of the $n-k$ contiguous subarrays $(A[0, k], A[1, k+1], \ldots, A[n-k, n])$, we’d like to know the maximum of that subarray. Write a function that, given an array $A$, returns an array containing the maximum of each of the $n-k+1$ subarrays.

Naive Solution: $O(n^2)$

One naive solution would be to linearly search for the maximum of every subarray.

def MSW_naive(A, k):
    res = []
    n = len(A)
    for i in range(n - k + 1):
        res.append(max(A[i:i+k]))
    return res

In this case, we’d perform $k$ comparison operations for each of the $n-k+1$ subarrays, resulting in a time complexity of $O(k(n-k+1)) \to O(nk)$. Of course, we can do better.

Sliding Window

The fundamental idea behind sliding window problems is that we need to store enough information about the current subarray to solve the subproblem. At every timestep $i$, only the $k$ elements from $A[i:i+k]$ are considered, so we’d also need a way to dispose of elements outside our subarray region.

A FIFO (First-In, First-Out) queue is an excellent candidate for this kind of problem. At every step, a new element can be added to the queue, while the oldest element is removed. The simplest sliding window problem would be to return a list containing each window:

def SW(A, k):
    res = []
    n = len(A)
    for i in range(n-k + 1):
        res.append(A[i:i+k])
    return res

Wow, practically identical to MSW_naive, how riveting.

Unfortunately, a queue alone won’t allow us to decrease our time bounds. To solve this problem, we’ll use a Python deque. Deque’s are two-sided queues with amortized constant-time insertion (pushing) and deletion (popping) for both sides of the datastructure. To be clear, Python’s deque calls pushing appending, and popping from and appending to a deque occurs on the “right side” of the datastructure, whereas popleft and appendleft occur on the left side. Now things get interesting.

Maximum Sliding Window: Deque

How can we solve the Maximum Sliding Window problem with a deque? We’ll satisfy two conditions for the deque at any time:

1. Anything in the deque must be a part of the subarray in question.
2. Anything older and smaller than some new element can be discarded.

The first is just a property of the sliding window technique. The second follows from the fact that if we’ve made it to some $i$th element already, then anything less than that $i$th element still in the deque will not be the max for the remainder of its time in the queue.

So, at every timestep $i$, we’ll store the index $i$, removing from most recent to least recent any indices $j$ with $A[j]$ less than $A[i]$. This satisfies our condition that we should discard anything that has no chance of being a max. We can then remove any elements that are too old to be considered for this subarray. Then, we must append our current $i$ to the deque. This is because it could be the case that $A[i]$ is the biggest element for the next $k$ steps, so we can’t throw it out. Another way to think about it is that $A[i]$ could be the largest element we’ve seen so far, so the deque would be empty, and we’d want to report $i$. Finally, we append the oldest element in our deque to our list of answers.

Here’s my implementation:

def maxSW(arr, k):
    d = deque()
    ans = []
    n = len(arr)
    for i in range(n):
    
        # remove elements from end that are smaller than new addition
        while d and arr[d[-1]] < arr[i]:
            d.pop()
            
        # make new addition
        d.append(i)
        
        # remove any elements that are too old
        if d[0] <= i - k:
            d.popleft()
            
        # the oldest element will be the largest in the deque
        # otherwise, we would have removed it in the while loop
        if i >= k-1:
            ans.append(arr[d[0]])
    return ans