Leetcode 239 - Sliding Window Maximum

Understanding the problem

Given an array of integers nums and an integer k, return the maximum element of each subarray of size k moving from left to right.

This problem can be solved by using a sliding window approach, where we maintain a window of size k and move it over the array, keeping track of the maximum element in each window.

Plan your solution

• Initialize an empty deque and an empty output array
• Add the first k elements of the array to the deque
• Iterate over the remaining elements in the array
  • Check if the current element is greater than the current maximum in the deque
  • If it is, remove all elements from the deque that are less than the current element and add the current element to the deque
  • If not, simply add the current element to the deque
  • Remove the first element from the deque if it is outside the current window
  • Append the deque’s last element to the output array
• Return the output array

Implement your solution

def maxSlidingWindow(nums, k):
    from collections import deque # importing deque from python's collections library
    dq = deque() # initializing an empty deque
    output = [] #initializing an empty output array
    for i in range(len(nums)): #iterating over the given array
        while dq and nums[i] > nums[dq[-1]]: 
            # while deque is not empty and the current element is greater than the last element in deque
            dq.pop() # remove the last element from deque
        dq.append(i) # add the current element to the deque
        if dq[0] == i-k:
            # if the first element in deque is outside the current window
            dq.popleft() # remove the first element from deque
        if i >= k-1:
            # if we have reached the kth element
            output.append(nums[dq[0]]) # append the first element of deque to output array
    return output

Test your solution

Let’s test our solution with the example inputs:

nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(maxSlidingWindow(nums, k))

Output: [3,5,5,5,6,7]

As we can see our solution is working correctly, the output is correct and matches the expected output.

In summary, we have successfully implemented a solution to Leetcode Problem 239 using sliding window approach with a time complexity of O(n) and a space complexity of O(k) where n is the size of the input array and k is the size of the sliding window.

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together