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