Deque and Sliding Window Max
Five prompts on the monotonic deque pattern: implementing sliding window maximum, the invariant that makes it O(n), and adjacent online-statistics applications.
Question Bank
Hard
Python
deque
sliding-window
algorithms
interview-prep
981 views
27
Implement slidingWindowMax(nums, k) returning an array of the maximum of every window of size k. Target O(n) time with a monotonic deque.
Examples
Example 1:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: A monotonic deque of indices keeps values strictly decreasing. Each index enters and leaves the deque at most once, giving O(n). The front of the deque is the index of the current window's max.Example 2:
Input: nums = [4, 4, 4, 4], k = 2
Output: [4, 4, 4]
Explanation: Repeated values do not break the invariant; equal values at the back are popped (using <=) so the deque only holds the most recent occurrence.4 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium