Day 30: Sliding Window Maximum: Sliding Window - leetcode - Python3

Buy me a coffee

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.

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]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

  SOLUTION

class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        result = []

        q = collections.deque()

        l = r = 0

        while r < len(nums):

            while q and nums[q[-1]] < nums[r]:

                q.pop()

            q.append(r)

            if l > q[0]: q.popleft()

            if (r+1) >= k:

                result.append(nums[q[0]])

                l += 1

            r += 1

        return result

Time Complexity: O(n): where n is the length of the input list nums

Space Complexity:O(k): where k is the size of the sliding window.

How it works:

1. The class Solution is defined to encapsulate the solution logic.

2. The maxSlidingWindow method takes two parameters: nums, which is a list of integers, and k, which represents the size of the sliding window. The method returns a list of integers representing the maximum elements in each sliding window.

3. The variables result, q, l, and r are initialized. result will store the maximum elements, q is a deque (double-ended queue) that will store indices of elements in the current window in descending order of their values, and l and r represent the left and right boundaries of the sliding window.

4. The code enters a while loop that continues until the right boundary r reaches the end of the list nums.

5. Inside the loop, there is another while loop that removes indices from the deque q if the corresponding elements in nums are smaller than the current element at index r. This ensures that the deque only contains indices of elements that are potentially the maximum within the window. The indices are popped from the right end of the deque using q.pop().

6. After ensuring that the deque is in the correct state, the current index r is appended to the deque using q.append(r).

7. The code then checks if the left boundary l is greater than the index at the left end of the deque (q[0]). If it is, it means that the maximum element in the window is outside the current window, so it is removed from the left end of the deque using q.popleft().

8. The code then checks if the window size is equal to or greater than k. If it is, it means that the window has reached the desired size. In this case, the maximum element in the current window is obtained by accessing nums[q[0]], and it is appended to the result list.

9. The left boundary l is incremented by 1 to slide the window to the right.

10. The right boundary r is incremented by 1 to process the next element in nums.

11. Once the loop finishes, the result list containing the maximum elements in each sliding window is returned.

In summary, the code efficiently finds the maximum element in each sliding window of size k by using a deque to keep track of potentially maximum elements. It slides the window through the input list and updates the deque accordingly to maintain the maximum elements within the window.