Sliding Window Maximum

QueueSliding WindowMonotonic Queue

30 min

Problem Statement

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

Example 1:

Input Nums:

-1

-3

k = 3

Result (Maxes):

Solution

A deque (double-ended queue) is perfect for this problem. We can use it to create a "monotonic queue" that stores indices of elements in the current window, always keeping the index of the largest element at the front.

Algorithm Steps

Initialize an empty deque and a result array.
Iterate through the input array with their indices.
Remove indices from the front of the deque if they are out of the current window.
Remove indices from the back of the deque if their corresponding values are less than the current value. This maintains the monotonic (decreasing) property.
Push the current index to the back of the deque.
Once the window is full, the maximum element for that window is at the front of the deque. Add it to the result.

Nums

-1

-3

Result

Deque (Indices)

Start.

Sliding Window Maximum Solution


from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        output = []
        q = deque()  # index
        l = r = 0

        while r < len(nums):
            # pop smaller values from q
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            # remove left val from window
            if l > q[0]:
                q.popleft()

            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1
        return output