Sliding Window Maximum

The problem is to find the maximum value in a sliding window of size ( k ) that moves through the given array. The window size and the array are provided, and the goal is to return a list containing the maximum value for each window position.

A good approach to solving this problem is to use a deque (double-ended queue). Here’s a step-by-step guide to the solution:

1. Initialize a Deque: Use a deque to keep track of the indices of elements in the current window. The deque should always store the indices in descending order of their corresponding values. So, the front of the deque will always have the maximum element of the current window.

2. Slide the Window: Iterate through the array, and for each element:

   • Remove the elements that are out of the current window from the front of the deque.
   • Remove the elements that are smaller than the current element from the back of the deque, as they will not be needed.
   • Append the current element to the back of the deque.
   • If the window is fully inside the array (i.e., the current index is greater or equal to ( k - 1 )), append the front element of the deque to the result, as it represents the maximum value in the current window.

3. Return the Result: The result array will contain the maximum values for each window position.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_values = []
        window = deque()

        for i, num in enumerate(nums):
            # Remove the indices that are out of the current window from the front
            while window and window[0] < i - k + 1:
                window.popleft()

            # Remove the indices of all elements that are smaller than the current element from the back
            while window and nums[window[-1]] < num:
                window.pop()

            # Add the current element to the back of the deque
            window.append(i)

            # If the window is fully inside the array, add the max value to the result
            if i >= k - 1:
                max_values.append(nums[window[0]])

        return max_values

This solution runs in O(n) time complexity, where n is the length of the input array, and O(k) space complexity, where k is the size of the window, as it stores at most k elements in the deque at any time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []

        max_values = []
        window = deque()

        # Iterate through the array
        for i, n in enumerate(nums):
            # Remove elements outside of the current window
            while window and window[0] < i - k + 1:
                window.popleft()

            # Remove elements smaller than the current element from the right side of the window
            while window and nums[window[-1]] < n:
                window.pop()

            window.append(i)

            # Add the maximum element of the current window to the result
            if i >= k - 1:
                max_values.append(nums[window[0]])

        return max_values

Identifying Problem Isomorphism

“Sliding Window Maximum” can be mapped to “Maximum Difference Between Node and Ancestor”.

The concept of maintaining a window to keep track of the maximum value in “Sliding Window Maximum” is similar to tracking the maximum difference in “Maximum Difference Between Node and Ancestor”. In the latter, instead of a sliding window, we traverse the tree but we are also aiming to keep track of a maximum value (the difference) as we go along.

“Sliding Window Maximum” is simpler as it deals with linear data (an array), whereas “Maximum Difference Between Node and Ancestor” introduces the additional complexity of working with a binary tree data structure.

Tackle “Sliding Window Maximum” first to get comfortable with the concept of maintaining maximum values, and then apply similar ideas in more complex data structures such as the binary tree in “Maximum Difference Between Node and Ancestor”.

“Sliding Window Maximum” involves finding the maximum number within every continuous subarray (or sliding window) of a given size in an array.

Two isomorphic problems are:

1. “485. Max Consecutive Ones”: This problem is simpler than “Sliding Window Maximum”. It involves finding the maximum number of consecutive 1s in an array, which is a specific form of a sliding window where the window size is the entire array and the maximum we’re seeking is the number of consecutive 1s.

2. “1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit”: This problem is more complex than “Sliding Window Maximum”. Here, you need to maintain a sliding window where the absolute difference between the maximum and minimum number within the window is less than or equal to a given limit.

The order of complexity from simple to more complex:

• “485. Max Consecutive Ones”
• “Sliding Window Maximum”
• “1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit”

These problems all share the common theme of performing a computation over a sliding window of data in an array.

10 Prerequisite LeetCode Problems

“239. Sliding Window Maximum” involves applying data structures such as arrays, queues, and specifically the concept of a sliding window. Here are 10 problems to build up to it:

1. “Maximum Subarray” (LeetCode Problem #53): This problem is about finding the contiguous subarray that has the maximum sum. It provides an understanding of contiguous array problems.

2. “Shortest Subarray with Sum at Least K” (LeetCode Problem #862): This problem also involves the concept of a sliding window, as well as the idea of maintaining a running total, similar to the Sliding Window Maximum problem.

3. “Moving Average from Data Stream” (LeetCode Problem #346): This problem provides practice for understanding and implementing sliding windows.

4. “Maximum Product of Three Numbers” (LeetCode Problem #628): This problem helps you to understand how to handle and calculate the maximum in an array.

5. “Queue Reconstruction by Height” (LeetCode Problem #406): This problem gives you an understanding of queue data structures.

6. “Binary Tree Right Side View” (LeetCode Problem #199): This problem provides an understanding of queue data structures in the context of binary trees.

7. “Rotate Array” (LeetCode Problem #189): This problem can give you more practice on manipulating arrays, which is a key aspect of the Sliding Window Maximum problem.

8. “Find All Anagrams in a String” (LeetCode Problem #438): This problem also involves sliding windows and can help you understand more advanced applications of the concept.

9. “Subarray Sum Equals K” (LeetCode Problem #560): This problem can provide further practice on the sliding window concept, along with the idea of maintaining a running total.

10. “Design Circular Deque” (LeetCode Problem #641): Understanding deque and its operations can be very helpful for the Sliding Window Maximum problem.

Working through these problems should provide a solid foundation in the skills and concepts necessary to tackle the “Sliding Window Maximum” problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import collections

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d.append(i)
            print("\t Added i to d")
            if d[0] == i - k:
                d.popleft()
            if i>=k-1:
                out.append(nums[d[0]])

        return out

Language Agnostic Coding Drills

1. Using collections module: This module provides alternatives to built-in container data types such as list, set, and dict. This problem uses the deque, a list-like container with fast appends and pops on either end.

2. Enumerate function: Enumerate is a built-in function of Python. It allows you to loop over a list and have an automatic counter, which is useful when you want to keep track of the current index.

3. Using List: List is a built-in data type in Python which can be used to store multiple items in a single variable. In this problem, we use it to store the elements of the sliding window.

4. Window sliding technique: This technique shows how to solve an array problem by moving a narrow window across the array. In this case, the window’s length is k.

5. Using deques: Deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. In this problem, it is used to efficiently maintain the maximum of the current window as the window slides.

6. Conditionals: The if statement in Python allows you to control if some block of code will be executed or not based on a condition being true or false.

7. Using append and pop functions: These functions are used to add an element to the end of the list and to remove an element from the end of the list respectively.

8. Using popleft function: This function is used to remove an element from the left end of the deque.

Here is how you would approach solving this problem:

1. Initialize a deque and an output list.
2. Loop over the input list using enumeration to access both the index and the value.
3. In each iteration, pop elements from the right of the deque that are less than the current element. This is because they are no longer candidates for the maximum value of the current and future windows.
4. Append the current index to the deque.
5. If the leftmost index in the deque equals the current index minus the window size, it means it’s out of bounds for the current window, so pop it from the left.
6. If the current index is greater than or equal to the window size minus 1, append the value at the leftmost index of the deque to the output. This is the maximum value for the current window.
7. Finally, return the output list.

Targeted Drills in Python

1. Using the collections module

   Drill: Create a program that uses deque from the collections module to append, pop from the right and pop from the left.

   1 2 3 4 5 6 7 8 9 10 11

   import collections d = collections.deque() d.append(5) d.append(10) print(d) # Output: deque([5, 10]) d.pop() print(d) # Output: deque([5]) d.appendleft(0) print(d) # Output: deque([0, 5]) d.popleft() print(d) # Output: deque([5])

2. Enumerate function

   Drill: Enumerate over a list and print out each index and corresponding value.

   1 2 3

   nums = [5, 10, 15, 20] for i, n in enumerate(nums): print(f"Index: {i}, Value: {n}")

3. Using Lists

   Drill: Create a list, append values to it, and access elements from it.

   1 2 3 4 5

   out = [] out.append(10) out.append(20) print(out) # Output: [10, 20] print(out[0]) # Output: 10

4. Window sliding technique

   Drill: Given a list of integers and a window size, write a program that prints out the maximum value in each window.

   1 2 3 4

   nums = [1, 3, -1, -3, 5, 3, 6, 7] k = 3 for i in range(len(nums) - k + 1): print(max(nums[i:i+k])) # Output: 3 3 5 5 6 7

5. Using deques

   Drill: Given a list of integers, write a program that appends each element to a deque, then pops each one from the right and prints it out.

   1 2 3 4 5 6 7

   import collections nums = [1, 2, 3, 4, 5] d = collections.deque() for n in nums: d.append(n) while d: print(d.pop()) # Output: 5 4 3 2 1

6. Conditionals

   Drill: Given a list of integers, write a program that prints out each element if it is greater than 5.

   1 2 3 4

   nums = [1, 6, 3, 8, 5] for n in nums: if n > 5: print(n) # Output: 6 8

7. Using append and pop functions

   Drill: Given a list of integers, write a program that appends each element to another list, then pops each one and prints it out.

   1 2 3 4 5 6

   nums = [1, 2, 3, 4, 5] new_list = [] for n in nums: new_list.append(n) while new_list: print(new_list.pop()) # Output: 5 4 3 2 1

8. Using popleft function

   Drill: Given a list of integers, write a program that appends each element to a deque, then pops each one from the left and prints it out.

   1 2 3 4 5 6 7 8 9

   import collections nums = [1, 2, 3, 4, 5] d = collections.deque() for n in nums: d.append(n) while d: print(d.popleft()) # Output: 1 2 3 4 5

For the final solution, you can combine the skills practiced in these drills. Start by initializing a deque and an output list. Use enumeration to iterate over the input list, popping elements from the right of the deque that are smaller than the current element and appending the current index to the deque. If the leftmost index in the deque is out of bounds of the current window, pop it from the left. Once you’ve moved past the first window, start appending the leftmost value of the deque to the output list. This is the maximum of the current window. Finally, return the output list.