Give an algorithm for the maximum of every window of width k in an array of length n, running in O(n) total. Prove the bound by counting deque operations, and say why a heap of size k is asymptotically worse.

Give an algorithm for the maximum of every window of width k in an array of length n, running in O(n) total. Prove the bound by counting deque operations, and say why a heap of size k is asymptotically worse.

Approach: Keep the window's candidate maxima in a deque whose values decrease from front to back, then count how many times a single index enters and leaves.

O(n). Maintain a deque of indices whose values strictly decrease from front to back. Before pushing index i, pop from the back while the value at the back is at most a[i], because such an element is dominated: it is both older and no larger, so it can never be the maximum of any window that contains i. Then pop the front if it has fallen out of the window and read the answer off the front. Each index is pushed exactly once and popped at most once, so the whole pass performs at most 2n deque operations and is linear time, with amortised cost O(1) per window even though a single step can pop many elements. A heap of size k gives O(n log k) because each insertion is logarithmic, and removing the element that leaves the window needs either a decrease-key with an index map or lazy deletion, both of which add constant factors that a deque of raw indices avoids entirely.

Follow-up: How would you answer maximum queries for arbitrary ranges given offline, and what preprocessing cost does that buy?

Key concepts: monotonic deque, amortised cost, dominated element, linear time.