45. Sliding Window Maximum
🔗 LeetCode Problem: 239. Sliding Window Maximum
📊 Difficulty: Hard
🏷️ Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Problem Statement
You are given an array of integers nums, 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.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
🎨 Visual Understanding
The Problem Visualized
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Window 1: [1, 3, -1] → max = 3
Window 2: [3, -1, -3] → max = 3
Window 3: [-1, -3, 5] → max = 5
Window 4: [-3, 5, 3] → max = 5
Window 5: [5, 3, 6] → max = 6
Window 6: [3, 6, 7] → max = 7
Result: [3, 3, 5, 5, 6, 7]
Key Observation: Need Efficient Maximum Tracking
Challenge:
- Window slides one position at a time
- Need maximum of each window
- Brute force: recalculate max for each window O(k) → Total O(n×k)
- Need: O(1) per window → Total O(n)
What we need:
- Add element to right
- Remove element from left
- Get maximum in O(1)
Approaches:
1. Brute Force: O(n×k) - check each window separately
2. Heap: O(n log n) - use priority queue
3. Monotonic Deque: O(n) - optimal solution
What is a Monotonic Deque?
A deque (double-ended queue) that maintains elements in
DECREASING order (for finding maximum)
Properties:
1. Front element is always maximum
2. When adding element, remove smaller elements from back
3. When sliding, remove elements outside window from front
Example:
nums = [1, 3, -1, -3, 5]
k = 3
Initial window [1, 3, -1]:
Add 1: deque = [1]
Add 3: Remove 1 (smaller), deque = [3]
Add -1: Keep 3, deque = [3, -1]
Max = 3 (front)
Slide to [3, -1, -3]:
Remove 1 (already gone from deque)
Add -3: Keep all, deque = [3, -1, -3]
Max = 3 (front)
Slide to [-1, -3, 5]:
Remove 3 (outside window)
deque = [-1, -3]
Add 5: Remove all smaller, deque = [5]
Max = 5 (front)
Visual Process
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Step 1: Build first window [1, 3, -1]
Add 1: deque = [1]
Add 3: 3 > 1, remove 1, deque = [3]
Add -1: -1 < 3, keep, deque = [3, -1]
Max = deque[0] = 3 ✓
Step 2: Slide to [3, -1, -3]
Remove index 0 (value 1): not in deque
Add -3: -3 < -1, keep, deque = [3, -1, -3]
Max = deque[0] = 3 ✓
Step 3: Slide to [-1, -3, 5]
Remove index 1 (value 3): deque[0] = 3, remove it
deque = [-1, -3]
Add 5: 5 > -1, remove all, deque = [5]
Max = deque[0] = 5 ✓
Step 4: Slide to [-3, 5, 3]
Remove index 2 (value -1): not in deque
Add 3: 3 < 5, keep, deque = [5, 3]
Max = deque[0] = 5 ✓
Step 5: Slide to [5, 3, 6]
Remove index 3 (value -3): not in deque
Add 6: 6 > 5, remove all, deque = [6]
Max = deque[0] = 6 ✓
Step 6: Slide to [3, 6, 7]
Remove index 4 (value 5): not in deque
Add 7: 7 > 6, remove all, deque = [7]
Max = deque[0] = 7 ✓
Result: [3, 3, 5, 5, 6, 7]
🎯 Approach 1: Brute Force
The Most Natural Thinking 💭
Core Logic:
For each window:
1. Find maximum element
2. Add to result
Simple but inefficient
Implementation
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result[i] = max;
}
return result;
}
⏰ Time: O(n × k) - n windows, each checked in O(k)
💾 Space: O(1) - excluding output array
🎯 Approach 2: Heap (Priority Queue)
Better but Not Optimal 💭
Core Logic:
Use max heap to track maximum:
1. Store (value, index) pairs in heap
2. Add elements to heap as window expands
3. Remove elements outside window by checking index
4. Top of heap is maximum (after removing invalid)
Key insight: Heap naturally maintains maximum at top
Challenge: Can't efficiently remove arbitrary elements
Solution: Lazy deletion - only remove when at top
Visual Explanation:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Heap stores: [value, index] pairs
Max heap: largest value at top
Window [1, 3, -1]:
Add [1, 0]: heap = [[1,0]]
Add [3, 1]: heap = [[3,1], [1,0]]
Add [-1, 2]: heap = [[3,1], [1,0], [-1,2]]
Max = 3 ✓
Window [3, -1, -3]:
Add [-3, 3]: heap = [[3,1], [1,0], [-1,2], [-3,3]]
Clean: [1,0] is outside window [1,3], but not at top
Top [3,1] is in window [1,3] ✓
Max = 3 ✓
Window [-1, -3, 5]:
Add [5, 4]: heap = [[5,4], [3,1], [1,0], [-1,2], [-3,3]]
Clean: Top [5,4] is in window [2,4] ✓
Max = 5 ✓
Implementation
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];
int[] result = new int[n - k + 1];
// Max heap: [value, index]
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// Build first window
for (int i = 0; i < k; i++) {
heap.offer(new int[]{nums[i], i});
}
// Remove elements outside window from top
while (heap.peek()[1] < 0) {
heap.poll();
}
result[0] = heap.peek()[0];
// Slide window
for (int i = k; i < n; i++) {
// Add new element
heap.offer(new int[]{nums[i], i});
// Remove elements outside current window [i-k+1, i]
while (heap.peek()[1] <= i - k) {
heap.poll();
}
result[i - k + 1] = heap.peek()[0];
}
return result;
}
⏰ Time: O(n log n) - n elements, each heap operation O(log n)
💾 Space: O(n) - heap can hold all elements
🔍 Step-by-Step Execution (Approach 2: Heap)
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
heap = [] (max heap: largest at top)
result = []
Building First Window [1, 3, -1]:
═══════════════════════════════════════════════════════════════════
Add nums[0] = 1:
heap.offer([1, 0])
heap = [[1, 0]]
Add nums[1] = 3:
heap.offer([3, 1])
heap = [[3, 1], [1, 0]]
(3 is larger, bubbles to top)
Add nums[2] = -1:
heap.offer([-1, 2])
heap = [[3, 1], [1, 0], [-1, 2]]
Clean elements outside window [0, 2]:
Top = [3, 1], index 1 >= 0 ✓ (in window)
result[0] = heap.peek()[0] = 3 ✓
Current state:
Window: [1, 3, -1]
Heap: [[3,1], [1,0], [-1,2]]
Result: [3]
Step 1: i = 3, Slide to [3, -1, -3]
═══════════════════════════════════════════════════════════════════
Window range: [1, 3] (indices i-k+1 to i)
Add nums[3] = -3:
heap.offer([-3, 3])
heap = [[3,1], [1,0], [-1,2], [-3,3]]
Clean elements outside window [1, 3]:
Top = [3, 1], is 1 <= 0? No ✓
Index 1 is in window [1, 3]
result[1] = heap.peek()[0] = 3 ✓
Current state:
Window: [3, -1, -3]
Heap: [[3,1], [1,0], [-1,2], [-3,3]]
↑ max ↑ outside but not cleaned yet
Result: [3, 3]
💡 Note: [1,0] is outside window but still in heap
This is OK - we use lazy deletion
It won't affect answer because [3,1] is larger
Step 2: i = 4, Slide to [-1, -3, 5]
═══════════════════════════════════════════════════════════════════
Window range: [2, 4]
Add nums[4] = 5:
heap.offer([5, 4])
heap = [[5,4], [3,1], [1,0], [-1,2], [-3,3]]
(5 is largest, bubbles to top)
Clean elements outside window [2, 4]:
Top = [5, 4], is 4 <= 1? No ✓
Index 4 is in window [2, 4]
result[2] = heap.peek()[0] = 5 ✓
Current state:
Window: [-1, -3, 5]
Heap: [[5,4], [3,1], [1,0], [-1,2], [-3,3]]
↑ max ↑ outside ↑ outside
Result: [3, 3, 5]
💡 Heap has old elements but they don't matter
5 is at top and in window - that's all we need!
Step 3: i = 5, Slide to [-3, 5, 3]
═══════════════════════════════════════════════════════════════════
Window range: [3, 5]
Add nums[5] = 3:
heap.offer([3, 5])
heap = [[5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
Clean elements outside window [3, 5]:
Top = [5, 4], is 4 <= 2? No ✓
Index 4 is in window [3, 5]
result[3] = heap.peek()[0] = 5 ✓
Current state:
Window: [-3, 5, 3]
Heap: [[5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
↑ max ↑ outside (all of these)
Result: [3, 3, 5, 5]
Step 4: i = 6, Slide to [5, 3, 6]
═══════════════════════════════════════════════════════════════════
Window range: [4, 6]
Add nums[6] = 6:
heap.offer([6, 6])
heap = [[6,6], [5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
(6 is largest, bubbles to top)
Clean elements outside window [4, 6]:
Top = [6, 6], is 6 <= 3? No ✓
Index 6 is in window [4, 6]
result[4] = heap.peek()[0] = 6 ✓
Current state:
Window: [5, 3, 6]
Heap: [[6,6], [5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
↑ max ↑ in window
Result: [3, 3, 5, 5, 6]
Step 5: i = 7, Slide to [3, 6, 7]
═══════════════════════════════════════════════════════════════════
Window range: [5, 7]
Add nums[7] = 7:
heap.offer([7, 7])
heap = [[7,7], [6,6], [5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
(7 is largest, bubbles to top)
Clean elements outside window [5, 7]:
Top = [7, 7], is 7 <= 4? No ✓
Index 7 is in window [5, 7]
result[5] = heap.peek()[0] = 7 ✓
Current state:
Window: [3, 6, 7]
Heap: [[7,7], [6,6], [5,4], [3,5], [3,1], [1,0], [-1,2], [-3,3]]
↑ max ↑ in ↑ out ↑ in (rest are outside)
Result: [3, 3, 5, 5, 6, 7]
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [3, 3, 5, 5, 6, 7]
═══════════════════════════════════════════════════════════════════
Key Observations:
1. Heap grows to contain many elements (including old ones)
2. We use "lazy deletion" - only remove when at top
3. As long as top element is in window, we don't care about rest
4. Time: O(n log n) - each element added/removed once
5. Space: O(n) - heap can grow to n elements
✅ Approach 3: Monotonic Deque (Optimal)
The Breakthrough Insight 💡
Core Logic:
Use monotonic deque (decreasing order):
Deque properties:
- Front: maximum element (or its index)
- Always in decreasing order
- Contains only potentially useful elements
Operations:
1. When adding element:
- Remove smaller elements from back
- Add current element to back
2. When sliding:
- Remove elements outside window from front
3. Get maximum:
- Front element is always maximum
Why this works:
If nums[i] >= nums[j] and i > j:
- nums[j] will NEVER be maximum in future windows
- Because nums[i] is larger and will stay in window longer
- So remove nums[j] from deque
Visual Explanation:
Why remove smaller elements?
nums = [1, 3, -1, ...]
When we see 3 after 1:
- 3 > 1
- 3 came after 1 (will stay in window longer)
- 1 can NEVER be maximum while 3 is in window
- Remove 1 from deque!
This keeps deque in decreasing order
And minimizes elements to track
Implementation
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // Store indices
for (int i = 0; i < n; i++) {
// Remove indices outside current window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove smaller elements from back
// They can never be maximum while current element is in window
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// Add current element index
deque.offerLast(i);
// Add maximum to result (after first window is complete)
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
⏰ Time: O(n) - each element added and removed at most once
💾 Space: O(k) - deque stores at most k elements
🔍 Step-by-Step Execution (Approach 3: Monotonic Deque)
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
deque = [] (will store indices)
result = []
Step 1: i = 0, nums[0] = 1
═══════════════════════════════════════════════════════════════════
Window not yet complete (i < k-1)
Remove outside window: nothing to remove
Remove smaller from back: deque is empty
Add current: deque = [0]
Window: [1, ?, ?]
deque indices: [0]
deque values: [1]
Step 2: i = 1, nums[1] = 3
═══════════════════════════════════════════════════════════════════
Window not yet complete (i < k-1)
Remove outside window: nothing to remove
Remove smaller from back:
nums[0] = 1 < nums[1] = 3
Remove index 0
deque = []
Add current: deque = [1]
Window: [1, 3, ?]
deque indices: [1]
deque values: [3]
💡 Why remove 1? Because 3 > 1 and 3 came later,
1 can never be max while 3 is in window!
Step 3: i = 2, nums[2] = -1
═══════════════════════════════════════════════════════════════════
Window complete! (i >= k-1)
Remove outside window: nothing to remove
Remove smaller from back:
nums[1] = 3 > nums[2] = -1
Don't remove, keep 3
Add current: deque = [1, 2]
Window: [1, 3, -1]
deque indices: [1, 2]
deque values: [3, -1]
Max = nums[deque[0]] = nums[1] = 3 ✓
result[0] = 3
Step 4: i = 3, nums[3] = -3
═══════════════════════════════════════════════════════════════════
Window slides: [3, -1, -3]
Remove outside window:
Window range: [1, 3] (indices i-k+1 to i)
deque[0] = 1, is 1 < 1? No, keep it
Remove smaller from back:
nums[2] = -1 > nums[3] = -3
Don't remove
Add current: deque = [1, 2, 3]
Window: [3, -1, -3]
deque indices: [1, 2, 3]
deque values: [3, -1, -3]
Max = nums[deque[0]] = nums[1] = 3 ✓
result[1] = 3
Step 5: i = 4, nums[4] = 5
═══════════════════════════════════════════════════════════════════
Window slides: [-1, -3, 5]
Remove outside window:
Window range: [2, 4]
deque[0] = 1, is 1 < 2? Yes, remove!
deque = [2, 3]
deque[0] = 2, is 2 < 2? No, keep
Remove smaller from back:
nums[3] = -3 < nums[4] = 5, remove 3
deque = [2]
nums[2] = -1 < nums[4] = 5, remove 2
deque = []
Add current: deque = [4]
Window: [-1, -3, 5]
deque indices: [4]
deque values: [5]
Max = nums[deque[0]] = nums[4] = 5 ✓
result[2] = 5
💡 5 is larger than everything before it, so remove all!
Step 6: i = 5, nums[5] = 3
═══════════════════════════════════════════════════════════════════
Window slides: [-3, 5, 3]
Remove outside window:
Window range: [3, 5]
deque[0] = 4, is 4 < 3? No, keep
Remove smaller from back:
nums[4] = 5 > nums[5] = 3
Don't remove
Add current: deque = [4, 5]
Window: [-3, 5, 3]
deque indices: [4, 5]
deque values: [5, 3]
Max = nums[deque[0]] = nums[4] = 5 ✓
result[3] = 5
Step 7: i = 6, nums[6] = 6
═══════════════════════════════════════════════════════════════════
Window slides: [5, 3, 6]
Remove outside window:
Window range: [4, 6]
deque[0] = 4, is 4 < 4? No, keep
Remove smaller from back:
nums[5] = 3 < nums[6] = 6, remove 5
deque = [4]
nums[4] = 5 < nums[6] = 6, remove 4
deque = []
Add current: deque = [6]
Window: [5, 3, 6]
deque indices: [6]
deque values: [6]
Max = nums[deque[0]] = nums[6] = 6 ✓
result[4] = 6
Step 8: i = 7, nums[7] = 7
═══════════════════════════════════════════════════════════════════
Window slides: [3, 6, 7]
Remove outside window:
Window range: [5, 7]
deque[0] = 6, is 6 < 5? No, keep
Remove smaller from back:
nums[6] = 6 < nums[7] = 7, remove 6
deque = []
Add current: deque = [7]
Window: [3, 6, 7]
deque indices: [7]
deque values: [7]
Max = nums[deque[0]] = nums[7] = 7 ✓
result[5] = 7
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [3, 3, 5, 5, 6, 7]
═══════════════════════════════════════════════════════════════════
Key Observations:
1. Deque size stays small (at most k elements)
2. Each element added once and removed at most once
3. Deque always in decreasing order
4. Front element always maximum
5. Time: O(n) - much better than heap!
6. Space: O(k) - much better than O(n)!
🔍 Edge Cases
Case 1: k = 1
Input: nums = [1, 3, -1, -3, 5], k = 1
Output: [1, 3, -1, -3, 5]
Explanation: Each window is single element
Case 2: k = n (entire array)
Input: nums = [1, 3, -1, -3, 5], k = 5
Output: [5]
Explanation: Single window
Case 3: Increasing array
Input: nums = [1, 2, 3, 4, 5], k = 3
Output: [3, 4, 5]
Explanation: Max always at right
Case 4: Decreasing array
Input: nums = [5, 4, 3, 2, 1], k = 3
Output: [5, 4, 3]
Explanation: Max always at left
Case 5: All same values
Input: nums = [3, 3, 3, 3], k = 2
Output: [3, 3, 3]
Case 6: Negative numbers
Input: nums = [-1, -3, -5, -7], k = 2
Output: [-1, -3, -5]
Case 7: Single element
Input: nums = [7], k = 1
Output: [7]
Case 8: Max at different positions
Input: nums = [1, 3, 1, 2, 0, 5], k = 3
Output: [3, 3, 2, 5]
Common Mistakes
Mistake 1: Storing values instead of indices (Approach 3)
❌ Wrong:
deque.offerLast(nums[i]); // Store value
✓ Right:
deque.offerLast(i); // Store index
Reason: Need index to check if element is outside window
Mistake 2: Wrong window boundary check
❌ Wrong:
if (deque.peekFirst() < i - k) {
// Off by one!
}
✓ Right:
if (deque.peekFirst() < i - k + 1) {
// Correct boundary
}
Reason: Window is [i-k+1, i]
Mistake 3: Using <= instead of < (Approach 3)
❌ Wrong:
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
✓ Right:
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
Reason: Keep equal elements (might be needed if max is removed)
Mistake 4: Adding result too early
❌ Wrong:
result[i] = nums[deque.peekFirst()];
// Added before window complete
✓ Right:
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
Reason: Wait until first window is complete
Mistake 5: Wrong result index
❌ Wrong:
result[i] = nums[deque.peekFirst()];
✓ Right:
result[i - k + 1] = nums[deque.peekFirst()];
Reason: Result array is smaller than nums
Mistake 6: Not checking deque empty
❌ Wrong:
while (nums[deque.peekLast()] < nums[i]) {
// Could throw exception if deque empty
}
✓ Right:
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
// Check empty first
}
Reason: Always check before peek/poll
Mistake 7: Not using lazy deletion in heap (Approach 2)
❌ Wrong:
// Try to remove specific element from heap
heap.remove([value, index]); // O(n) operation!
✓ Right:
// Only remove from top when outside window
while (heap.peek()[1] <= i - k) {
heap.poll();
}
Reason: Heap doesn't support efficient arbitrary deletion
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Brute Force
Time: O(n × k)
Space: O(1)
Use: Only for understanding
Pros: Simple
Cons: Too slow
Approach 2: Heap (Priority Queue)
Time: O(n log n)
Space: O(n)
Use: When monotonic deque is not known
Pros: Better than brute force, familiar data structure
Cons: Extra space, still not optimal
Key: Lazy deletion - only remove when at top
Approach 3: Monotonic Deque (RECOMMENDED)
Time: O(n)
Space: O(k)
Use: Optimal solution, best for interviews
Pros: Optimal time and space
Cons: Requires understanding of monotonic deque
Key: Remove useless elements proactively
🔑 The Core Insight
Heap vs Monotonic Deque:
═══════════════════════════════════════════════════════════════
Heap Approach:
- Keep all elements in heap
- Lazy deletion: only remove when at top
- Max is at top, but might be outside window
- Need to check and clean before using
- Time: O(n log n), Space: O(n)
Monotonic Deque Approach:
- Only keep USEFUL elements
- Proactive deletion: remove immediately
- Max is always at front AND in window
- No cleaning needed
- Time: O(n), Space: O(k)
Why Deque is Better:
1. Smaller space: O(k) vs O(n)
2. Faster time: O(n) vs O(n log n)
3. Simpler logic: no cleaning needed
Monotonic Deque Data Structure:
═══════════════════════════════════════════════════════════════
A deque that maintains elements in sorted order:
- For maximum: decreasing order (largest at front)
- For minimum: increasing order (smallest at front)
Properties:
1. Front element is always answer (max/min)
2. Can add/remove from both ends in O(1)
3. Each element added/removed at most once → O(n) total
Why Monotonic?
═══════════════════════════════════════════════════════════════
When we see larger element:
nums[i] > nums[j] where i > j
Insight: nums[j] is USELESS for future windows!
- It's smaller than nums[i]
- It will leave window before nums[i]
- So remove nums[j] from consideration
This keeps deque small and in decreasing order!
Algorithm Template (Approach 3):
═══════════════════════════════════════════════════════════════
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 1. Remove elements outside window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 2. Remove smaller elements from back
// They can never be max while current is in window
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// 3. Add current element index
deque.offerLast(i);
// 4. Record maximum (after first window complete)
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
Key Operations:
═══════════════════════════════════════════════════════════════
pollFirst() - Remove from front (outside window)
pollLast() - Remove from back (smaller elements)
offerLast() - Add to back (current element)
peekFirst() - Get front (maximum element)
Why Store Indices Not Values?
═══════════════════════════════════════════════════════════════
Need to check if element is outside window:
if (deque.peekFirst() < i - k + 1) {
// This index is outside current window
}
Can't do this with just values!
Time Complexity Analysis:
═══════════════════════════════════════════════════════════════
Each element:
- Added to deque once: O(1)
- Removed from deque once: O(1)
- Total: O(n)
NOT O(n × k) because:
- We don't process each window separately
- Each element processed exactly twice (add + remove)
🎯 Pattern Recognition
Problem Type: Sliding Window with Range Queries
Core Pattern: Monotonic Deque
When to Apply:
✓ Sliding window with fixed size k
✓ Need min/max in each window
✓ Want O(n) time (better than O(n log n))
✓ Can't use simple tracking (values change)
Recognition Keywords:
- "Sliding window maximum/minimum"
- "k-sized window"
- "Each window" or "all windows"
- Better than heap solution needed
Monotonic Deque Use Cases:
┌─────────────────────────────────────────┐
│ Maximum in window → Decreasing deque │
│ Minimum in window → Increasing deque │
│ Both sides access → Use deque │
│ Only one side → Use stack │
└─────────────────────────────────────────┘
Related Concepts:
- Monotonic Stack (similar but one-directional)
- Heap (slower but handles dynamic k)
- Segment Tree (handles range updates)
Related Problems:
- Longest Continuous Subarray With Absolute Diff <= Limit (LC 1438)
- Constrained Subsequence Sum (LC 1425)
- Shortest Subarray with Sum at Least K (LC 862)
🧠 Interview Strategy
Step 1: "Need maximum of each k-sized window"
Step 2: "Brute force is O(n×k), can we do better?"
Step 3: "Heap gives O(n log n), but optimal is O(n)"
Step 4: "Use monotonic deque for O(n) solution"
Step 5: "Deque maintains decreasing order"
Step 6: "Front is always maximum"
Step 7: "Each element added/removed once"
Key Points to Mention:
For Heap Approach:
- Use max heap to track maximum
- Store [value, index] pairs
- Lazy deletion: only remove when at top
- Check if top element is in current window
- Time: O(n log n), Space: O(n)
- Works but not optimal
For Monotonic Deque Approach:
- Fixed-size sliding window
- Need efficient maximum tracking
- Monotonic deque (decreasing order)
- Store indices not values
- Remove from front: outside window
- Remove from back: smaller elements
- Front element is maximum
- Each element processed at most twice
- O(n) time, O(k) space
- Better than heap O(n log n)
Why Deque Works:
"If we see a larger element after a smaller one,
the smaller can never be maximum while the larger
is in the window. So we remove the smaller element.
This keeps our deque in decreasing order, with the
maximum always at the front."
Critical Insight:
"The key is recognizing that we don't need to keep
ALL elements - only potentially useful ones. An element
is useless if there's a larger element that came after
it, because that larger element will outlast it."
Comparison:
"Heap uses lazy deletion and keeps all elements,
while monotonic deque uses proactive deletion and
only keeps useful elements. That's why deque is
faster and uses less space."
This is a classic monotonic deque problem! 🏆
📝 Quick Revision Notes
🎯 Core Concept:
Monotonic deque maintains decreasing order. Front = maximum. Remove smaller from back, remove outside from front. Each element processed once.
⚡ Quick Implementation (Approach 3 - Optimal):
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// Remove outside window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove smaller from back
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// Add current
deque.offerLast(i);
// Record max
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
⚡ Quick Implementation (Approach 2 - Heap):
import java.util.Arrays;
import java.util.PriorityQueue;
class Test {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int index = 0;
int[] res = new int[len - k + 1]; // simple intuitive by checking the example
// Takes an int array of 2 values and give back the largest one when polled.
// int[0] is actual value and int[1] is index of that value int[0] in array
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// First window
for (int i = 0; i < k; i++) {
pq.offer(new int[] { nums[i], i }); // value should be first as seen above
}
res[index++] = pq.peek()[0]; // no need to do any cleanup in the first window.
for (int i = k; i < len; i++) {
pq.offer(new int[] { nums[i], i }); // add new value to PQ.
// Now we need to poll PQ and add it to the result.
// Before adding to the result, ensure that the value is in the correct window
// If not poll it and check for next value. Repeat till you find the value from
// the existing window.
// When k = 3 and i = 3, index shoud be >= 1 and <= 3 (1, 2, 3)
// So, when incoming polled index < 1 (i - k + 1), poll it
while (pq.peek()[1] < i - k + 1) {
pq.poll();
}
res[index++] = pq.peek()[0];
}
return res;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(Arrays.toString(t.maxSlidingWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3)));
}
}
🔑 Key Insights:
Approach 2 (Heap): - Data structure: Max heap (PriorityQueue) - Store: [value, index] pairs - Lazy deletion: Only remove when at top - Clean: Before reading max, remove outside elements - Time: O(n log n) - each element O(log n) - Space: O(n) - heap grows to n elements
Approach 3 (Monotonic Deque): - Data structure: Deque (ArrayDeque in Java) - Store: Indices, not values - Order: Decreasing (front = max) - Remove front: Elements outside window (index < i - k + 1) - Remove back: Smaller elements (can't be max) - Add: Always to back (current index) - Get max: Front element (deque.peekFirst()) - Window complete: When i >= k - 1 - Result index: i - k + 1 - Time: O(n) - each element add/remove once - Space: O(k) - deque size at most k
🎪 Memory Aid:
"HEAP = lazy clean! DEQUE = proactive remove! Deque WINS!"
Think: "Useless = smaller AND older! Remove immediately!"
💡 The Key Difference:
Heap:
- Keep ALL elements
- Clean when needed (lazy)
- Time: O(n log n)
- Space: O(n)
Deque:
- Keep ONLY useful elements
- Remove immediately (proactive)
- Time: O(n)
- Space: O(k)
Deque is better!
🔥 Why Each Approach?
Heap:
+ Familiar data structure
+ Easy to understand
- Not optimal (time and space)
Use: When deque is unknown
Deque:
+ Optimal time O(n)
+ Optimal space O(k)
- Requires understanding monotonic deque
Use: For best solution!
🎯 The Useless Element Insight:
If nums[i] > nums[j] and i > j:
→ nums[j] is USELESS forever!
→ It's smaller AND will leave window first
→ Remove it from deque!
This is why deque stays decreasing!
And why each element touched only once!
Related Patterns
- Longest Continuous Subarray With Absolute Diff <= Limit (LC 1438)
- Constrained Subsequence Sum (LC 1425)
- Shortest Subarray with Sum at Least K (LC 862)
- Next Greater Element (LC 496) - Monotonic Stack
Happy practicing! 🎯