Solution: Sliding Window Maximum

Statement

Given an integer array 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 array and find the maximum in each window separately. We iterate over the input array, calculating the maximum element in each window linearly, and then adding it to the output array. 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 array. Once we are done iterating the 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 array 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 an array for the window.

Optimized approach using sliding window

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