09/18/2017

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.

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.

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.

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

- Anything in the deque must be a part of the subarray in question.
- 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
```

08/22/2018

Toward the Light: Behind the Scenes

07/01/2018

Arch Linux: Chromebook C720 Webcam Microphone Disappeared

06/21/2018

SSH: How to Set Up a Simple Local Media Server

02/28/2018

Pacman: File Conflicts

01/17/2018

Making an Arch Linux USB Flash Install Medium

01/17/2018

Arch Linux: Post-Install Notes

01/15/2018

Binary Classification Metrics

01/14/2018

Probabilitistic Classification

01/09/2018

Classification and Perceptron

01/08/2018

Linear Regression: Bayesian Approach, Normal Conjugacy

01/08/2018

Nonlinearity: Basis Functions

01/04/2018

Linear Regression: A Probabilistic Approach

12/30/2017

Linear Regression: A Mathematical Approach

12/20/2017

2017 Reflections: A Year of Curating

12/19/2017

Introduction to Regression: K-Nearest Neighbors

12/18/2017

Welcome to my Miscellaneous Blog!

12/18/2017

A Definitive Arch Linux Install Guide for the Chromebook C720

10/01/2017

C4D: Volume Effector

09/18/2017

Algorithms: Maximum Sliding Window

09/10/2017

Introduction to Inference: Coins and Discrete Probability

09/05/2017

C4D: Unreliable Booles

08/30/2017

Welcome to my Tech Blog!

08/30/2017

Welcome to my Problem Solving Blog!

Previous: Introduction to Inference: Coins and Discrete Probability | Next: C4D: Volume Effector