LeetCode · #239

Sliding Window Maximum Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #239

🏗️

Pattern

Monotonic Deque — track max in O(1)

You are given an array of integers nums and an integer k representing the size of a sliding window that moves from left to right. Return an array containing the maximum element in each window position.

Example

 Input: nums = [1,3,-1,-3,5,3,6,7],  k = 3 Output: [3,3,5,5,6,7]
// Windows: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7 

Constraints

 • 1 ≤ nums.length ≤ 10⁵ • -10⁴ ≤ nums[i] ≤ 10⁴ • 1 ≤ k ≤ nums.length 

Section Two · Approach 1

Brute Force — O(n · k)

For each window position, scan all k elements to find the maximum. Simple but slow when k is large.

Problem: O(k) per window, O(n·k) total. A monotonic deque maintains candidates in decreasing order, giving O(1) amortized max lookups — O(n) total.

Java — Brute Force

 class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
for (int i = 0; i <= nums.length - k; i++) {
int max = nums[i];
for (int j = i + 1; j < i + k; j++)
                max = Math.max(max, nums[j]);
            result[i] = max;
        }
return result;
    }
}

Python — Brute Force

 class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Metric	Value
Time	O(n · k)
Space	O(1) — excluding output

Section Three · Approach 2

Monotonic Deque — O(n)

Maintain a deque (double-ended queue) of indices in decreasing order of their values. The front of the deque always holds the index of the current window's maximum. When adding a new element, remove all smaller elements from the back (they'll never be the max while the new element exists). Remove the front if it's outside the window.

💡 Mental model: Imagine a queue of people waiting to be "king of the window." When a taller person (larger number) arrives, all shorter people in front of them leave — they'll never be king while the tall person is in the window. The tallest person always stands at the front. When someone's time in the window expires, they leave from the front.

Algorithm

Step 1: Create an empty deque storing indices.
Step 2: For each index i:
Step 3: Remove front if it's outside the window: deque.peekFirst() < i - k + 1.
Step 4: Remove all back elements with values ≤ nums[i] (they're useless).
Step 5: Push i to back of deque.
Step 6: If i ≥ k - 1 (window is full): result.add(nums[deque.peekFirst()]).

🎯 Why "monotonic"?:

The deque is always in decreasing order of values.
Every time we add a new element, we evict all smaller elements from the back — maintaining the monotonic property.
This ensures the front is always the max, and each element is pushed/popped at most once — O(n) total.

Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Monotonic Deque — indices in decreasing value order

Notice:

Each index is pushed once and popped at most once. Total operations across all iterations = O(n).
The deque front always holds the window maximum — O(1) to read.

Section Five · Implementation

Code — Java & Python

Java — Monotonic Deque

 import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores indices for (int i = 0; i < nums.length; i++) {
// Remove elements outside the window if (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
                deque.pollFirst();
// Remove smaller elements from back — they'll never be max while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])
                deque.pollLast();

            deque.offerLast(i);
// Window is full — record the max (front of deque) if (i >= k - 1)
                result[i - k + 1] = nums[deque.peekFirst()];
        }
return result;
    }
}

Python — Monotonic Deque

 from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq = deque() # stores indices
result = []
for i in range(len(nums)):
# Remove element outside window if dq and dq[0] < i - k + 1:
                dq.popleft()
# Remove smaller elements from back while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n · k)	O(1)	Scan k elements per window
Max-Heap (PQ)	O(n log n)	O(n)	Lazy deletion from heap; log n per op
Monotonic Deque ← optimal	O(n)	O(k)	Each element pushed/popped once. Deque holds at most k.

Why not a max-heap?:

A max-heap gives O(log n) per insert/delete — but removing elements that have left the window requires either lazy deletion (mark as stale and skip when popped) or a tree-based structure.
The monotonic deque is simpler and strictly O(n): each element enters and leaves at most once.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k == 1	`[1, 3, -1]`	Each element is its own window → output equals input.
k == n	`[1, 3, -1]`	Single window → output is [max(nums)] = [3].
All same	`[5, 5, 5], k=2`	Deque always has one element. Output is [5, 5].
Descending	`[4, 3, 2, 1], k=2`	Deque front is always the leftmost (largest). Output: [4, 3, 2].
Ascending	`[1, 2, 3, 4], k=2`	Each new element evicts all prior. Deque always size 1. Output: [2, 3, 4].
Negative values	`[-1, -3, -2], k=2`	Works the same — max of negatives. Output: [-1, -2].

⚠ Common Mistake: Using < instead of <= when evicting from the back: nums[deque.peekLast()] <= nums[i]. Using strict < leaves equal elements in the deque, which is harmless for correctness but wastes space. Using <= keeps the deque minimal and ensures only the rightmost occurrence of equal values survives — cleaner and slightly more efficient.

← Back to Sliding Window problems

LearningTree

LC 239 · Sliding Window Maximum — Solution & Explanation | DSA Guide