We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sliding Window Maximum

Difficulty: Hard

Problem Description

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Key Insights

  • A sliding window approach allows us to efficiently keep track of the maximum value in the current window.
  • Using a deque (double-ended queue) can help in maintaining the maximum values in a way that allows for O(1) access to the maximum while pushing and popping elements.
  • The maximum element for each window can be determined by removing elements that are out of the window and maintaining the order of the maximum elements.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(k)

Solution

The problem can be solved using a deque to maintain the indices of the elements in the current window. The deque will store indices of elements in a way that the values they point to are in decreasing order. As the window slides:

  1. Remove indices that are out of the bounds of the current window.
  2. Remove elements from the back of the deque while the current element is greater than the elements at those indices, ensuring that the deque always has the maximum element at the front.
  3. The maximum for each window can be found at the front of the deque once the window size reaches k.

Code Solutions

from collections import deque

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    result = []
    dq = deque()  # Will store indices of the elements in nums

    for i in range(len(nums)):
        # Remove indices that are out of the bounds of the current window
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove elements from the back of the deque while the current element is greater
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        # Add the current index to the deque
        dq.append(i)
        
        # Once we have filled the first k elements, we can start adding results
        if i >= k - 1:
            result.append(nums[dq[0]])  # The max of the window is at the front of the deque

    return result
← Back to All Questions