Problem of The Day: Sliding Window Maximum

3 min read 761 words

Problem Statement

Brute Force - Sliding Window - TLE

Intuition

My initial thought is to iterate through the array using a sliding window approach. For each window of size ‘k’, I can find the maximum element and append it to the result list. This approach ensures that we efficiently find the maximum element in each window.

Approach

I will maintain two pointers, ‘start’ and ‘end,’ to represent the sliding window. As I move the window, I’ll check if its size equals ‘k’. If so, I’ll find the maximum element in that window using the ‘max’ function and append it to the result list. Then, I’ll move the window by incrementing the ‘start’ pointer.

Complexity

• Time complexity: O(n * k) where ‘n’ is the length of the input array. This is because, for each window of size ‘k’, we are finding the maximum element in that window.

• Space complexity: O(1) as we are using a constant amount of space for the pointers and the result list.

Code

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

Editorial Solution

Approach: Monotonic Deque

The algorithm utilizes a monotonic decreasing queue, implemented as a deque, to efficiently find the maximum element in each sliding window of a given array. It begins by processing the first ‘k’ elements, ensuring that the deque maintains a decreasing order of values. This guarantees that the front of the deque always represents the maximum element in the current window. As the algorithm slides through the array, it adjusts the deque to track the current window, removing indices that are no longer part of the window and eliminating smaller elements from the back. The maximum element in the current window is consistently at the front of the deque, resulting in a streamlined approach to identifying maximum values for each window.

Complexity

• Time complexity: O(n)

• Space complexity: O(k) where k is the size of the deque

Code

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque() # Store indices of elements in the current window
        res = []

        # 1. Process the first 'k' elements to initialize the first window
        for i in range(k):
            # Maintain monotonic property: remove indices of elements smaller than current
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)

        # The front of the deque holds the index of the largest element for the first window
        res.append(nums[dq[0]])

        # 2. Slide the window from index 'k' to the end of the array
        for i in range(k, len(nums)):
            # If the index at the front is outside the current window, remove it
            if dq and dq[0] == i - k:
                dq.popleft()
            
            # Maintain monotonic property: only keep elements that could potentially be max
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()

            dq.append(i)
            # The current maximum is always at the front of the deque
            res.append(nums[dq[0]])

        return res