#20 Hard Time O(n) Space O(n) Animated

Sliding Window Maximum

Return the maximum element in each sliding window of size k.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Sliding window with a maintained constraint

Expand to include new information, then shrink only until the window is valid again.

Approach: Monotonically Decreasing Deque

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Expand to include new information, then shrink only until the window is valid again.

Common Pitfall

Update the best answer only when the window satisfies the problem constraint.

Description

Return the maximum element in each sliding window of size k.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Monotonically Decreasing Deque

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Expand the right edge.
Update window state.
Shrink from the left while invalid.
Record the best valid window.

def maxSlidingWindow(nums, k):
    res = []
    q = collections.deque()
    l = r = 0
    
    while r < len(nums):
        while q and nums[q[-1]] < nums[r]:
            q.pop()
        q.append(r)
        
        if l > q[0]:
            q.popleft()
            
        if (r + 1) >= k:
            res.append(nums[q[0]])
            l += 1
        r += 1
        
    return res

Minimum Window Substring

Sliding Window Maximum

Steps

Description

Constraints

Tags

Solution — Monotonically Decreasing Deque