hardCodingConceptMidSenior
Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?
Keep a deque of indices whose values strictly decrease from front to back. Each step drops the front if it has left the window, pops smaller or equal values from the back, then appends. The front is the window maximum. Each index enters and leaves once, so it is amortised O(n), against O(n log k) for a balanced tree.
5 min readUpdated 2026-10-09Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Keep a monotonic deque of indices whose values strictly decrease from front to back. At each step, drop the front if it has slid out of the window. Then pop every back entry whose value is no larger than the new one, and append the new index. The front is the window's maximum. Each index enters once and leaves once, so the sliding window maximum costs amortised O(n) time and O(k) space.
Was this answer helpful?
Likely follow-ups
- Get O(n) without a deque by splitting the array into blocks of size k with prefix and suffix maxima. Why does every window touch at most two blocks?
- The window is defined by timestamps rather than a fixed count. What changes in the expiry check?
- Track the minimum and the maximum together to find the longest subarray whose spread stays under a limit. How many deques?
- The values arrive as an unbounded stream. What does the deque cost in memory for a window of one million?
Related questions
- Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.hardAlso on amortised-analysis and arrays5 min
- For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.mediumAlso on amortised-analysis and arrays4 min
- Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.mediumAlso on amortised-analysis4 min
- Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.mediumAlso on amortised-analysis5 min