Sliding Window Maximum

Sliding WindowDeque

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,-1,-3,5,3,6,7], k = 3

nums: [1, 3, -1, -3, 5, 3, 6, 7], k: 3

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

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

Solution

A highly efficient way to solve this problem is by using a deque (double-ended queue). The deque will store indices of elements in the current window, and we'll maintain it in a way that the first element is always the index of the maximum value in the window.

Algorithm Steps

Initialize an empty deque and a results array.
Iterate through the `nums` array with a pointer `r`.
While the deque is not empty and the element at the back of the deque is smaller than `nums[r]`, pop from the back. This maintains the decreasing order of values in the deque.
Add the current index `r` to the back of the deque.
If the index at the front of the deque is out of the current window's bounds (i.e., `deque[0] < l`), remove it from the front.
Once the window is full (i.e., `r + 1 >= k`), the maximum for the current window is at the front of the deque. Add `nums[deque[0]]` to the results.

Sliding Window Maximum

Deque Approach

Progress1 / 1

Ready to start the visualization

nums

-1

-3

Deque (indices)

Result

Sliding Window Maximum Solution


import collections

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        output = []
        q = collections.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