LC 239 - Sliding Window Maximum

Question

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

Links

Question here and solution here

Solution

concept

The key idea here is to use a monotonic decrease queue to keep track the elements within the window.
For every new element added to the window, we remove all elements that are smaller than the new element, thus queue[0] is always the maximum element in the window
If the left pointer is at the maximum element, we remove it from the queue as the window will slide over in the next step

code

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        out = []
        r,l = 0,0
        q = collections.deque()
        while r < len(nums):
            while q and q[-1] < nums[r]:
                q.pop() # remove all elements smaller than the new element
            q.append(nums[r])
            if r+1 >= k:
                out.append(q[0])
                if nums[l] == q[0]: # left pointer is at the maximum number
                    q.popleft()
                l+=1
            r+=1
        return out

Complexity

time: $O(n)$
space: $O(n)$