Solution: Sliding Window Maximum

Statement

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

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

Our first solution uses the sliding window technique to solve the problem. However, ...