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 of each window.
Hint 1A brute force scans each window — O(n·k). Can you do better?▼
For each window of size k, find the max in O(k). Total: O(nk). But if you could maintain the max as the window slides, you'd get O(n). What data structure helps?
Hint 2Use a monotonic deque — it keeps indices in decreasing value order.▼
Before adding index r, pop all indices from the back of the deque whose values are smaller than nums[r] — they can never be a future window maximum. The front of the deque always holds the max index of the current window.
Hint 3Remove indices from the front when they slide out of the window.▼
The deque front is valid only if its index ≥ l. When the window slides (l advances), check if the front index is out of range and popleft if so. Then record nums[deque[0]] as the window maximum.
🌐 Real-World Analogy
Real-Time Sensor Monitoring
Industrial IoT systems track the peak temperature across the last k sensor readings in real time. A naive approach re-scans k readings each second. The monotonic deque approach processes each reading exactly once, giving O(n) total — essential for systems processing millions of sensor events per second where even a small constant factor matters.
Optimal Approach — Monotonic Deque
O(n) Time
📊
Decreasing Deque of Indices
Time O(n)Space O(k)
We maintain a deque of indices whose corresponding values are in decreasing order. The front always holds the index of the current window's maximum. Each element is pushed and popped at most once.
1For each new index r, pop from the back while the back element's value is smaller than nums[r] — those can never be a max.
2Append r to the deque back.
3If the deque front is out of the current window (index < l), popleft.
4Once the window is full (r + 1 ≥ k): record nums[deque[0]] as the max, advance l.
Since every element enters and exits the deque exactly once, total work is O(n). The deque holds at most k elements at any time, giving O(k) space.
Discussion
…