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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sliding Window Maximum

Number: 239

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, Google, Oracle, TikTok, Apple, Goldman Sachs, Bloomberg, Microsoft, Booking.com, tcs, DE Shaw, Uber, Adobe, Citadel, Coupang, Autodesk, Gameskraft, MongoDB, Yandex, Roku, Rubrik, Nutanix, Salesforce, Palo Alto Networks, PhonePe, Zenefits

Problem Description

Given an array of integers (nums) and a window size (k), the task is to slide the window from the left of the array to the right by one position at a time and return an array of the maximum values in each window.

Key Insights

  • Use a deque (double-ended queue) to maintain the indices of potential maximum elements in a decreasing order.
  • Ensure that the deque always has the current window's indices by removing elements that fall outside the current window.
  • Only add elements that are greater than the ones at the back of the deque, thus preserving a monotonic decreasing order.
  • The maximum for the current window is at the front of the deque.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums, since each element is processed at most twice. Space Complexity: O(k), as the deque stores indices for at most k elements at any time.

Solution

The solution uses a monotonic deque to maintain indices of potential maximum elements in the current window. As the window slides, we:

  1. Remove indices from the front if they are out of the window.
  2. Remove indices from the back if the current element is larger, because they cannot be the maximum if the current element is in the window.
  3. Append the current index.
  4. After the first k elements, the element at the front of the deque is the maximum for that window. This approach ensures that each element is pushed and popped from the deque only once, achieving an overall O(n) time complexity.

Code Solutions

from collections import deque

def maxSlidingWindow(nums, k):
    # Create a deque to store indices of elements in the current window
    deq = deque()
    result = []
    
    for i, num in enumerate(nums):
        # Remove indices from the front if they are out of the current window
        if deq and deq[0] == i - k:
            deq.popleft()
        
        # Remove elements from the back while the current number is larger 
        # than the number at the indices stored in the deque
        while deq and nums[deq[-1]] < num:
            deq.pop()
        
        # Append the current index to the deque
        deq.append(i)
        
        # If we've hit the window size, append the current max to result
        if i >= k - 1:
            result.append(nums[deq[0]])
    
    return result

# Example usage:
# print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
← Back to All Questions