Sliding Window Maximum

Problem

You are given an integer array nums and a window size k. A window of size k starts at the left edge of the array and slides one position to the right at a time until it reaches the right edge. For each of the n - k + 1 window positions, report the maximum value inside the window. Return these maxima as a list, in order.

Examples

• nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7] — e.g. the first window [1, 3, -1] has max 3; the third window [-1, -3, 5] has max 5.
• nums = [1], k = 1 → [1] — a single window containing the single element.
• nums = [9, 8, 7, 6], k = 2 → [9, 8, 7] — a strictly decreasing array: each window’s max is its left element.

Constraints

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= len(nums)
• With n and k both up to 10^5, the O(n·k) rescan-every-window approach is up to 10^10 operations — you need roughly O(n log n) or O(n).

Think about it first

TL;DR

Monotonic deque of indices — O(n) time, O(k) space.

Approach 1 — Brute force (rescan every window)

Compute max over each window independently.

from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    result = []
    for i in range(n - k + 1):
        window = nums[i:i + k]
        result.append(max(window))
    return result

Complexity: O(n · k) time, O(k) space (the slice).

With n and k both up to 10^5, this is about 10^10 comparisons, too slow for the given constraints.

Approach 2 — Max-heap with lazy deletion

The insight: a max-heap always knows the largest value it holds; the only problem is elements that have slid out of the window. Instead of deleting them eagerly (heaps can’t remove arbitrary elements cheaply), store each value with its index and discard stale entries lazily — only when they surface at the top. A binary heap is the classic priority-queue structure giving O(log n) insertion and O(log n) removal of the extremum; Python’s heapq is a min-heap, so push negated values.

import heapq
from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    heap: List[tuple] = []          # (-value, index)
    result = []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        if i >= k - 1:
            while heap[0][1] <= i - k:      # top is out of window
                heapq.heappop(heap)
            result.append(-heap[0][0])
    return result

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

• After pushing indices 0–2, top is (-3, 1) → emit 3.
• i=3: push (-(-3), 3); top still (-3, 1), index 1 ≥ 3−3+1 → in window → emit 3.
• i=4: push (-5, 4); new top (-5, 4) → emit 5.
• i=5: top (-5, 4) still in window → emit 5.
• i=6: push (-6, 6) → top → emit 6. Stale entries like (-3, 1) linger harmlessly below.
• i=7: push (-7, 7) → top → emit 7.

Result [3, 3, 5, 5, 6, 7].

Complexity: O(n log n) time — every element is pushed once and popped at most once, each at O(log n); the heap can hold up to n entries because deletion is lazy, so O(n) space.

Approach 3 — Monotonic deque

The insight: if nums[j] >= nums[i] with j > i, then index i can never again be a window maximum — any window containing i from now on also contains the newer, bigger j. So on arrival of each element, throw away every smaller-or-equal element waiting behind it. What survives is a deque of indices whose values are strictly decreasing from front to back — a monotonic deque, the classic structure for range-extremum-over-sliding-window queries. The front is always the current maximum; expiry is a single check on the front index.

from collections import deque
from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq: deque = deque()             # indices, values strictly decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:     # x dominates the tail
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                  # front slid out of window
            dq.popleft()
        if i >= k - 1:
            front = dq[0]
            result.append(nums[front])
    return result

Walkthrough with nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (deque shown as values):

Result [3, 3, 5, 5, 6, 7]. Note index expiry never fired here because domination already evicted old elements; on [9, 8, 7, 6] with k = 2 it’s the expiry check doing the work instead.

Complexity: O(n) time — each index enters and leaves the deque at most once, so all the while pops across the whole run total ≤ n — and O(k) space (the deque holds indices of one window).

Common pitfalls

• Storing values in the deque instead of indices — you then can’t tell when the front has slid out of the window.
• Popping the tail only on strictly-smaller (< instead of <=): correctness survives, but duplicates pile up; conversely popping the front by value comparison is outright wrong — the front leaves on index expiry only.
• Off-by-one on the expiry test: the window at position i covers indices i-k+1 … i, so the front is stale when dq[0] <= i - k (not < i - k).
• Emitting from the very first iteration instead of waiting until i >= k - 1, producing n outputs instead of n - k + 1.

Pattern takeaway

When a sliding window must answer an extremum query (max/min) rather than a count or sum, plain running totals don’t survive the departure of the extreme element. The reusable tool is the monotonic deque: discard every element dominated by a newer one, keep the survivors sorted by construction, and both endpoints update in amortized O(1). The same structure powers “shortest subarray with sum ≥ K”, constrained-jump DPs, and any “max/min over the last k items” stream query.