Sliding Window Maximum
Difficulty: Hard · Topics: Sliding Window, Deque, Array
Difficulty: Hard | Tags: Sliding Window, Deque, Array
Description
Given an array of integers nums and a window size k, return the maximum value in each sliding window of size k as the window moves from left to right.
Implement:
maxSlidingWindow(nums, k) → int[]
Examples
Example 1:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation:
Window [1, 3, -1] → max = 3
Window [3, -1, -3] → max = 3
Window [-1, -3, 5] → max = 5
Window [-3, 5, 3] → max = 5
Window [5, 3, 6] → max = 6
Window [3, 6, 7] → max = 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [9, 8, 7, 6, 5], k = 2
Output: [9, 8, 7, 6]
Example 4:
Input: nums = [1, 1, 1, 1], k = 3
Output: [1, 1]
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
Hints
Hint 1
Brute force: for each window, scan for max → O(nk). Can you do better?
Hint 2
Use a Deque (double-ended queue) to maintain indices of useful elements. Keep the deque decreasing — the front always has the max.
Hint 3
When sliding the window: (1) remove indices out of window from front, (2) remove smaller elements from back, (3) add current index, (4) front of deque is the answer.
Complexity
- Optimal: O(n) time, O(k) space using a monotonic deque.
---
## Bonus Problems