Sliding Window Maximum (LeetCode 239)

Problem

You are given an integer array nums and a window of size k that slides from the very left of the array to the very right, one position at a time. Return the maximum of each window. Aim for O(n) time.

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]

Constraints: 1 ≤ nums.length ≤ 10⁵ | −10⁴ ≤ nums[i] ≤ 10⁴ | 1 ≤ k ≤ nums.length

🪟 Array & window

🚇 Deque of indices · values always decreasing front → back

⬅FRONT
max 👑

empty

➡BACK
newest

deque operations: 0 brute force would compare: —

👑 current window max🗑️ popped from back (smaller, older)⌛ popped from front (left the window) index is in the deque

Variables

—

window

—

deque (idx)

—

nums[front]

—

💡 Step Logic

Press ▶ Play or Next to begin.

Ready

0 / 0

Pick an example and press Play.

Algorithm

Deque stores indices; their values are always decreasing front → back

For each i: if the front index left the window (≤ i − k), pop it from the front ⌛

While the back value ≤ nums[i], pop it from the back 🗑️ (it can never be a max again)

Push i to the back

Once the window is full (i ≥ k − 1), the answer is nums[front] 👑

Time

O(n)

Space

O(k)

🧠 Why it's O(n)

Every index is pushed once and popped at most once, so the deque does at most 2n operations in total, no matter how big k is. Checking every window directly costs (n − k + 1) · k comparisons, which is O(n·k). The watch-out: store indices, not values, so you can tell when the front has slid out of the window.

⚠️ Edge cases

k = 1 → every element is its own max. k = n → one window, one answer. Decreasing array → nothing is ever popped from the back and the deque fills up to k. Duplicates → using ≤ drops the older copy, which is safe because the newer one lasts longer.