DSA problem
Sliding Window Maximum
You are given an array of integers nums, and 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 maximum element in each window.
A brute-force approach scans each window independently in O(k), producing O(n * k) total work; this is too slow for the constraints (n up to 10^5). A heap-based solution gets O(n log k) but still pays a logarithmic factor for each comparison and must lazily evict expired indices.
The classic optimal solution is the monotonic deque. We maintain a double-ended queue of indices into nums whose corresponding values are strictly decreasing from front to back. With this invariant, the front of the deque is always the index of the maximum element in the current window.
Two updates are performed on each new index i: first, remove indices from the back while their values are not greater than nums[i] — they can never be the max of any future window that also contains i. Second, pop the front whenever it has fallen out of the window (i.e., front <= i - k). After processing index i, once i >= k - 1, record nums[deque.front] as the maximum of the current window. Each index is pushed and popped at most once, so total time is O(n) and auxiliary space is O(k).
Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]nums = [1], k = 1[1]nums = [9,11], k = 2[11]Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.