Solution: Find Maximum in Sliding Window

Statement#

Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.

Note: If the window size is greater than the list size, we consider the entire list as a single window.

Constraints:

• $1$ $\leq$ arr.length $\leq$ $10^3$
• $-10^4$ $\leq$ arr[i] $\leq$ $10^4$
• $1$ $\leq$ w

Solution#

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

Naive approach#

A naive approach is to slide the window over the input list and find the maximum in each window separately. Here’s how the algorithm works:

• We create an array, current_window to store the contents of the current $w$-length window.

• We iterate over the first window and add its elements to current_window.

• We linearly calculate the maximum element in current_window, and add it to the output array.

• In each subsequent iteration, we remove the first element of current_window and then append the incoming element in the window to it. We then again calculate the maximum linearly and add it to the output array. This process is repeated for each window.

• Finally, when we have traversed the entire input array, we return the output array containing the maximums of all $(n-w+1)$ windows.

The time complexity of this approach is $O(n \times w)$. Since we only iterate over the input list once to find all the windows, the time complexity of this part will be $O(n)$. Furthermore, removing the first element, appending the outgoing element, and finding the maximum element in the window take $O(w)$ time.

The space complexity of this approach is $O(w)$, since we maintain an array for the window.

Optimized approach using sliding window#

Our first solution uses the sliding window technique to solve the problem. However, there is much room for improvement. In the following section, we will gradually optimize our naive approach to reduce the time complexity to $O(n)$.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Firstly, instead of adding values to current_window, we use their indexes. By doing this, we can easily check which index has fallen out of the current window and remove it.

Secondly, we process the elements of the first window as follows:

• Every time we add a new index to current_window, we clean it up, i.e., we iterate backward over current_window, starting from the end, and remove all the indexes whose corresponding values in the input list are smaller than or equal to the new element in the window. Let’s understand how this step benefits us. Whenever a new element enters the window, all the previous elements smaller than the current element can no longer be the maximum in the current or any subsequent windows containing the new element. This is because all the subsequent windows holding the indexes of the removed elements will also include the new, bigger element. Since this new element is bigger than those elements, keeping those smaller elements in current_window is unnecessary.

• A key detail to note here is that we perform the clean-up step starting with the second element added to the first window. As a result, even in the first window, we will have excluded all elements smaller than the maximum of that window that occurs before it in the input list.

• Let’s understand this using an initial frame of five elements, $[2, 4, 5, 3, 1]$. When the index of $4$ is added to current_window, it causes the index of $2$ to be deleted. The addition of the index of $5$ causes the index of $4$ to be deleted. However, the addition of the indexes of $3$ and $1$ does not trigger any deletions. At the end of this clean-up process, current_window contains the indexes, $[2, 3, 4]$, corresponding to the values, $[5, 3, 1]$.

• Once we have cleaned up the first window, the remaining indexes in current_window will be stored in the descending order of their values. Now, let’s imagine the other possibility where the first frame actually contains $[2, 4, 5, 1, 3]$. Here, the addition of the index of $1$ does not trigger any deletion, but $3$ does cause the index of $1$ to be deleted. current_window now holds the indexes $[2, 4]$, corresponding to the values $[5, 3]$, which are sorted in descending order. Since we’ve examined both possibilities (either the elements in nums after element $5$ are in descending order, or they aren’t), we can be sure that, after the clean-up process, the index of the maximum element in the first window will always be stored at the start of current_window.

• We append the value corresponding to the index at the start of current_window to our output list.

Next, we iterate over the remaining input list. For each element, we perform the clean-up step as we did for the elements of the first window.

One difference when processing the second and all subsequent windows, compared to the processing of the first window, is an additional check that is carried out before we append the current element in nums to current_window. We check whether the first index in current_window is still a part of the current window. If not, we remove the first index from current_window.

Lastly, when the entire input list has been processed, one window at a time, we return the output list containing the maximum of each window.

Let’s understand this algorithm with the help of an illustration:

Now, let’s analyze the algorithm in terms of complexity. We are still moving over the input list in $O(n)$ time and using the sliding window approach to maintain current_window. Inside the loop, we append the new element to current_window, which takes $O(1)$ time. The time complexity of the clean-up step is $O(1)$, which is explained in detail in the complexity analysis of the final solution. Lastly, we remove the index that no longer falls in the current window. As this element is removed from the start of the list, the time complexity of removing this index will be $O(w)$. Therefore, the overall time complexity of this solution will be $O(n \times w)$. The space complexity of this solution is $O(w)$, as we maintain a list to store the indexes of significant elements from the current window.

In the first optimization, we eliminated the additional creation of current_window, reducing the time complexity by a significant factor. Let’s see if we can further improve our solution.

At the moment, we are incurring two kinds of costs. The first cost is of iterating over the input array while sliding the window forward. No matter what approach we use, we can not eliminate this cost. The second cost is of removing the first element from the list current_window. The list data structure will always impose this cost. So, we need a data structure that removes elements in constant time from the end and from the start.

The data structure that supports constant-time removals from both ends is a deque. A deque is a double-ended queue where the Push() and Pop() operations work in $O(1)$ time at both ends. Therefore, just by maintaining current_window as a deque instead of as a list, we can reduce the time complexity of the above solution to $O(n)$. This is the most optimized solution for solving this problem. The space complexity of the solution will still be $O(w)$, the maximum number of elements in the current window, stored in the deque.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution can be divided into the following parts:

1. First, we validate the inputs. If the input list is empty, we return an empty list and if the window size is greater than the list length, we set the window to be the same size as the input list.

2. Then, we process the first $w$ elements of the input list. We will use a deque to store the indexes of the candidate maximums of each window.

3. For each element, we perform the clean-up step, removing the indexes of the elements from the deque whose values are smaller than or equal to the value of the element we are about to add to the deque. Then, we append the index of the new element to the back of the deque.

4. After the first $w$ elements have been processed, we append the element whose index is present at the front of the deque to the output list as it is the maximum in the first window.

5. After finding the maximum in the first window, we iterate over the remaining input list. For each element, we repeat Step 3 as we did for the first $w$ elements.

6. Additionally, in each iteration, before appending the index of the current element to the deque, we check if the first index in the deque has fallen out of the current window. If so, we remove it from the deque.

7. Finally, we return the list containing the maximum elements of each window.

Time complexity#

The input parameters of the function are a list of integers, and an integer specifying the size of the window. In the discussion that follows, we will use $n$ to represent the size of the list of integers, and $w$ to represent the size of the window.

To get a clearer understanding of the time complexity of our solution, we need to consider the different ways in which the values in the input list change. The values in the list can be:

1. Strictly increasing
2. Strictly decreasing
3. Constant
4. Mixed, for example, increasing, decreasing, constant, then decreasing again, then constant, then increasing, then constant and then decreasing

On the surface, we might expect our solution to take $O(n * w)$, but that would be no better than the naive solution. When we look closer at our solution, it comes down to figuring out how many times the clean-up loop actually runs. This is the loop that pops all elements from the deque that are smaller than the new element in the window.

Let’s consider the first case, that is, when the values in the array are strictly increasing. The first time the window moves forward, the new element is larger than all the other elements in the deque, so we have to perform the pop() operation $w$ times. Then, in all the subsequent steps, the pop() operation is performed only once, as the deque will only contain one element from this point onwards. The number of subsequent steps is $n-w$. So, the complexity in this case is $O(w+n-w)$, that is, $O(n)$.

In the second case, every time the window moves forward, the new element is smaller than all the other elements in the deque, so the popleft() operation is only performed once in every subsequent step, to remove the element which does not fall in the window anymore. So, the time complexity in this case is $O(n - w + 1)$, that is, $O(n-w)$.

In the third case, the same behaviour is repeated as in the second case, so the time complexity is $O(n-w)$ here too.

Finally, in the fourth case, the time complexity for increasing values as well as decreasing and constant values will be the same as explained above. The only other situation is when the values increase after staying constant, or right after a sequence of decreasing numbers. In either case, we incur a cost of $O(w)$, as we clean up the deque using the pop() operation. If there is an increase in value after every $w$ elements, we pay the $O(w)$ cost to clean up the deque. This can only happen $\frac{n}{w}$ times. The cost of filling up the deque while the elements are constant or decreasing will be $O(w)$. So, the total cost with such data will be $O((w+w)(\frac{n}{w}))$, that is, $O(2w(\frac{n}{w}))$ or $O(n)$.

Hence, the time complexity of the solution, considering the worst of these four cases, is $O(n)$.

Space complexity#

The space complexity of this solution is $O(w)$, where $w$ is the window size.