Sliding Window Maximum hard

Problem Statement

Given an array nums and an integer k, return the maximum value in each sliding window of size k. A sliding window is a contiguous subarray of size k that moves one position at a time.

Example 1

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

Example 2

Input: nums = [1], k = 1 Output: [1]

Steps

The naive approach would be to iterate through all possible windows and find the maximum in each. This is inefficient, leading to O(n*k) time complexity. A more efficient solution uses a deque (double-ended queue) to maintain the indices of potential maximum values within the current window.

1. Initialization: Create a deque dq to store indices.
2. Sliding Window: Iterate through the nums array.
3. Deque Maintenance:
   • Remove elements from the rear of dq: While the deque is not empty and the last element's value is less than or equal to the current element's value, remove it. This ensures that the deque only contains indices of elements that are potentially maximums.
   • Remove elements from the front of dq: If the element at the front of the deque is outside the current window, remove it.
   • Add the current element's index to the rear of dq:
4. Result: If the window size has been reached (i >= k - 1), append the value at the index at the front of the deque (the maximum) to the result list.

Explanation

The deque maintains a monotonically decreasing sequence of indices. The element at the front of the deque is always the index of the maximum element in the current window. By removing smaller elements from the rear and elements outside the window from the front, we efficiently track the maximum within each sliding window.

Code

from collections import deque

def maxSlidingWindow(nums, k):
    """
    Finds the maximum value in each sliding window of size k.

    Args:
        nums: The input array of numbers.
        k: The size of the sliding window.

    Returns:
        A list containing the maximum value in each sliding window.
    """
    n = len(nums)
    if n == 0 or k == 0:
        return []
    
    dq = deque()  # Deque to store indices
    result = []

    for i in range(n):
        # Remove elements smaller than the current element from the rear
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        # Add the current element's index to the rear
        dq.append(i)
        
        # Remove elements outside the current window from the front
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Add the maximum to the result if the window size is reached
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Complexity

• Time Complexity: O(n), where n is the length of nums. Each element is added and removed from the deque at most once.
• Space Complexity: O(k), as the deque stores at most k indices.