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)$ ...