239. Sliding Window Maximum

Hard

Problem:

Given an array nums, find the maximum sliding window of size k by moving the sliding window to the right end.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

https://leetcode.com/problems/sliding-window-maximum

Solution:

Brute Force

Because the maximum value of the window is calculated every time, in this case, the time complexity is $O(n)$.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return nums
            
        results = []
        for i in range(0, len(nums) - k + 1):
            results.append(max(nums[i: i+k]))
        
        return results

Deque

Time Limit Exceeded

It's difficult to improve the part where the sliding window has to move one step at a time. Therefore, there is no choice but to minimize the calculation of the maximum value. By saving the previous maximum value and only checking if the new value is larger as it moves one step at a time, and recalculating the entire window only when the maximum value falls out of the window, it can be improved into a form (FIFO - First In First Out).

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results = []
        window = collections.deque()
        current_max = float('-inf')        
        for i, v in enumerate(nums):
            window.append(v)
            if i < k - 1:
                continue
                
            # Replace if the newly added value is greater 
            # than the existing maximum value
            if current_max == float('-inf'):
                current_max = max(window)
            elif v > current_max:
                current_max = v
            
            results.append(current_max)
            
            # Reset when the maximum value falls out of the window
            if current_max == window.popleft():
                current_max = float('-inf')
        return results

Better Implementation

class Solution:
    def maxSlidingWindow(self, nums, k):
        dq = deque()
        res = []

        for i in range(k):
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)

        res.append(nums[dq[0]])

        for i in range(k, len(nums)):
            if dq and dq[0] == i - k:
                dq.popleft()
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()

            dq.append(i)
            res.append(nums[dq[0]])

        return res

Reference: https://www.youtube.com/watch?v=DfljaUwZsOk