Sliding Window Maximum

If you can derive this solution from first principles, you’ve learned the core monotonic queue pattern.

Pattern Summary

This problem uses the [Monotonic queue] pattern.

• Recognition: Forward-sliding window of fixed width $k$, rolling maximum query, older values become permanently irrelevant once beaten by newer values.
• Core Invariant: The deque stores only undominated candidates, strictly decreasing by value and increasing by index.
• Transformation: Replace $O(k)$ brute-force rescanning or $O(\log k)$ lazy heap purges with $O(1)$ amortized eager dominance eviction.

$\rightarrow$ Read the full theoretical foundation: [Monotonic queue]

Real-World Analogues

Infrastructure

Rolling Peak Request Latency
An Envoy or NGINX edge proxy records request latency continuously. Operations dashboards display the highest latency observed during the last 30 seconds. As each new request arrives, the oldest request expires. Recomputing the maximum for every update burns CPU because consecutive windows overlap almost completely.

Distributed Systems & Telemetry

Maximum Queue Depth
A distributed task scheduler tracks the deepest worker queue backlog over the last five minutes to detect bursty traffic without rescanning historical metrics every second.

Security & Rate Limiting

Peak Authentication Failures
An API gateway tracks the largest burst of failed login attempts across a moving 5-minute window to detect credential-stuffing attacks in real time without batch aggregation lag.

Interview Abstraction

LeetCode 239 strips away the network headers and queue metadata to ask the exact underlying mathematical question: given an array nums and a window size k, return the maximum value in every forward-sliding window of length k in $O(n)$ total time.

Why This Problem Matters

This problem isolates one foundational idea: permanent dominance.

Because there are no complex state transitions or auxiliary transformations, it is the purest environment to master the core deque mechanics before moving to DP or prefix sums.

Recognition

Reach for this pattern when:

• ✓ The window slides strictly forward (left-to-right, never rewinds).
• ✓ You must report the maximum at every step.
• ✓ Rescanning the window feels wasteful ($O(nk)$ bottleneck).
• ✓ A max-heap feels close but incurs unnecessary $O(\log k)$ overhead.

The Mental Shift

Naive Thought   → "Find the maximum element inside each active window."
Correct Thought → "Delete older elements the moment a larger or equal newcomer arrives."

Once element $B$ arrives behind element $A$ with $B \ge A$, element $A$ is permanently dead. Every future window covering $A$ will also cover $B$.

Solution Evolution

Why This Beats a Heap

The heap answers: “What is the largest value I have seen?”
The deque answers: “What is the largest value that is still relevant?”

That single distinction eliminates the need for lazy deletion and drops every window update from $O(\log k)$ to amortized $O(1)$.

From Pattern → Code

Every monotonic queue problem maps to three explicit policy decisions:

# 1. EVICT: Prune tail candidates that are dominated by incoming value x
while dq and nums[dq[-1]] <= x:
    dq.pop()

# 2. STORE: Store index so we can verify positional window expiry
dq.append(i)

# 3. EXPIRE: Drop front if its position slid out of the active window
if dq[0] <= i - k:
    dq.popleft()

Optimal Solution

from collections import deque
from typing import List

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    if k == 1:
        return nums[:]
    
    dq = deque()  # stores indices; values nums[dq] strictly decreasing
    out = []
    
    for i, x in enumerate(nums):
        # 1. Evict dominated candidates from tail
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        
        # 2. Append current candidate index
        dq.append(i)
        
        # 3. Expire head if out of window
        if dq[0] <= i - k:
            dq.popleft()
        
        # 4. Record answer once first full window is reached
        if i >= k - 1:
            out.append(nums[dq[0]])
            
    return out

Visual Walkthrough

Tracing nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3.
Band W is the active window; caret M is the front of the deque (the window’s max).

Complexity Analysis

Edge Cases

Common Mistakes

• ❌ Storing values instead of indices: Storing raw values makes positional expiry (dq[0] <= i - k) impossible.
• ❌ Emitting before the window is full: Emitting before index k - 1 leaks invalid partial-window extrema.
• ❌ Expiring after recording: Recording the answer before checking dq[0] <= i - k returns stale, expired elements.
• ❌ Using < instead of <=: Allows duplicate equal values to accumulate, bloating deque memory without refreshing the expiration position.
• ❌ Confusing the deque with the window: Expecting len(dq) == k. The deque only contains the undominated frontier, not the entire window.

Problem Progression

Mastering this problem enables you to solve a progression of harder variations:

1. Sliding Window Minimum (Medium): Invert eviction rule to >= x.
2. Continuous Subarrays (Medium): Maintain two concurrent monotonic deques (min and max) over a variable-length sliding window.
3. Jump Game VI (Medium): Apply monotonic deque over dynamic programming transitions ($O(n)$ DP optimization).
4. Constrained Subsequence Sum (Hard): DP transition optimization with non-negative lower bounds.
5. Shortest Subarray with Sum at Least K (Hard): Monotonic deque over prefix sums with greedy left-pointer pops.

Principal Lens

If you remember one thing: The deque is not the window. It is the frontier of undominated candidates. Once an arrival is larger than an older neighbor, the older neighbor is permanently dead.

def max_sliding_window_brute(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    return [max(nums[i : i + k]) for i in range(len(nums) - k + 1)]

import heapq

def max_sliding_window_heap(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    
    heap = []  # (-value, index) for max-heap
    out = []
    
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        
        if i >= k - 1:
            # Remove expired maxima until the root belongs to the current window
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            out.append(-heap[0][0])
            
    return out