Solution: Sliding Window Maximum

Statement

You are given an array of integers nums and a sliding window of size w that moves from left to right across the array, shifting one position at a time.

Your task is to find the maximum value within the current window at each step and return it.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

• $1 \leq$ w $\leq$ nums.length

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. We iterate over the input list, calculating the maximum element in each window linearly, and then adding it to the output list. In each subsequent iteration, we update the current window by removing the first element from the current window and adding the incoming element of the input list. Once we are done iterating the input list, we return the output list, 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, adding the incoming 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 a list for the window.

Optimized approach using sliding window

We’ll use a sliding window technique combined with a deque (double-ended queue). The idea is to maintain a deque of indexes of elements in the current window such that their corresponding values are in decreasing order. The front of the deque will always store the index of the maximum element of the window.

As we iterate through nums, for each element:

• We remove smaller elements from the back of the deque since they can’t be the maximum for the current or any future window containing the current element.

• If the index at the front of the deque falls out of the current window, we remove it.

• After processing the first w elements, we start appending the value at the front of the deque to the result list, as it represents the maximum for the current window.

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

Build the solution using a list

Our goal is to avoid recomputing the maximum value from scratch at every step. To do this, we maintain a list called currentWindow, which stores the indexes of useful elements. By useful, we mean elements that could still be the maximum in the current or any upcoming window. The list is kept in decreasing order of values in nums, i.e., the first index will always point to the largest element in the current window.

We start by iterating through the first w elements in the first window:

1. Before adding a new index, i, to currentWindow, we first check if any existing indexes point to smaller or equal elements. These are removed from the back of the list, because they cannot become maximum while the new (larger) element is in the window using cleanUp(i, currentWindow, nums).

2. Then, we append the current index, i, to currentWindow.

3. After building the first window, we add the maximum (the value at the first index in currentWindow) to the output list.

4. For the remaining elements, we slide the window forward:

   1. In each iteration, we again remove smaller or equal elements from the back of currentWindow. using the cleanUp function.

   2. If the index at the front of the list points to an element that is no longer in the current window, we remove it.

   3. After removing old indexes, we append the current index.

   4. We then record the current maximum by adding nums[currentWindow[0]] to the output.

Each of these steps makes sure that currentWindow always holds exactly the right elements:

1. Older elements that can no longer be maximum are removed.

2. Smaller elements that will be “dominated” by newer, larger elements are removed.

3. The largest element’s index always remains at the front, so getting the max at each step is constant-time.

A key detail to note here is that we start removing smaller elements from 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 occur earlier in the input list.

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