Sliding Window Maximum

PracticeNeetCode ↗LeetCode ↗

Given an array nums and a window size k, return an array of the maximum value in each window of size k as it slides from the start of nums to the end.

Example

Key Pointers

• A monotonic decreasing deque holds indices, not values, so the front of the deque is always the current window's maximum.
• Before pushing a new index, pop indices off the back whose values are smaller than the incoming value — they can never become the max again while a larger, more recent value is still in the window.
• Pop the front index once it slides outside the window; checking indices (not values) is what makes that possible in O(1).

Step-by-Step Analysis

1. Initialize an empty deque dq (stores indices) and an empty result list.
2. For each index right, value val: while dq isn't empty and the value at its back index is smaller than val, pop from the back.
3. Append right to dq.
4. If the index at the front of dq has fallen out of the window, pop it from the front.
5. Once the window has filled (right >= k - 1), append the value at the front index to result.
6. Return result.

Complexity

Time: O(n) — every index is pushed and popped from the deque at most once — Space: O(k)

Code

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()
    result = []

    for right, val in enumerate(nums):
        while dq and nums[dq[-1]] < val:
            dq.pop()
        dq.append(right)

        if dq[0] <= right - k:
            dq.popleft()

        if right >= k - 1:
            result.append(nums[dq[0]])

    return result

Code Explanation

How the solution above works, piece by piece.

1. The deque holds indices whose values are decreasing from front to back, so the front is always the window's maximum.
2. Before adding right, pop every smaller value off the back. They can never be a maximum again: val is bigger and stays in the window longer.
3. if dq[0] <= right - k: dq.popleft(): the front index has slid out of the window, so drop it.
4. Once the first full window exists (right >= k − 1), append nums[dq[0]].
5. Each index is pushed and popped at most once: O(n) total, versus O(n·k) for scanning every window.

Visual Walkthrough

Running it on nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Video Explanation

NeetCode — Sliding Window Maximum, LeetCode 239