LeetEye LeetEye
Medium Sliding Window ~5 min

Sliding Window Maximum

sliding-window sliding-window-maximum

Problem

You are given an array of integers nums, and 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.

Examples

Example 1
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Example 2
Input: nums = [1], k = 1
Output: [1]
Key Insight

Use a monotonic decreasing deque. Front is always the current max. Remove elements that can't be max for future windows.

Monotonic decreasing deque of indices: remove smaller from back (useless candidates), remove expired from front (out of window). Front is always current max.

How to Approach This Problem

Pattern Recognition: When you see keywords like sliding window maximum sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 A max-heap seems natural for tracking maximum. The issue is:
Answer: Heaps can't handle removing arbitrary elements efficiently
When the window slides, we must remove the element leaving the window. Heaps don't support efficient arbitrary removal (only top removal).
2 When a larger element enters the window, all smaller elements to its left:
Answer: Can never be the maximum while the larger element is in the window
A smaller element can only become max if all larger elements leave. But the new larger element entered AFTER, so it leaves later. The smaller elements will never be max.
3 The deque should store:
Answer: Indices of potential maximum candidates
We store indices because (1) we can get values from indices, and (2) we need indices to check if element is still in window.
4 The deque maintains elements in:
Answer: Decreasing order (from front to back)
Front is the maximum. Each subsequent element is smaller but might become max later when larger elements leave.
5 Before adding nums[i] to deque, we:
Answer: Remove all smaller elements from back
Elements smaller than nums[i] will never be max while nums[i] is in window. Remove from back (LIFO) to maintain deque order.
6 We remove from front when:
Answer: Front index is outside the current window
If front index ≤ current index - k, it's no longer in the window. Remove it.

Solution

from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq = deque()  # Store indices, decreasing order by value
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside current window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Remove smaller elements from back
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Add max to result once window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Complexity Analysis

Time O(n)
Space O(k)

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye