269. Maximum of All Subarrays of Size K

Given an array of n integers and a window size k, print the maximum element of every contiguous subarray (window) of size k, in order from left to right, space-separated.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the window size k. Output: Print the maximum of every size-k contiguous window, left to right, space-separated.

1 <= k <= n <= 10^5

'Lazy deletion' (checking validity only when reading the top, rather than eagerly removing stale entries the moment they expire) is a broadly reusable heap technique whenever entries can become 'stale' over time without needing immediate cleanup.

For every contiguous window of size k sliding across an array, find that window's maximum value. Brute force: For every window position, scan all k elements directly to find the maximum - this costs O(n*k), too slow for large n and k. Optimised: A max-heap (with lazy deletion of out-of-window entries, checked only when reading the top) avoids ever eagerly removing stale entries - each element is pushed once and popped at most once over the whole algorithm's lifetime, giving true O(n log n) overall despite looking like it might need per-window cleanup.

Maintain a max-heap of (value, index) pairs. As the window slides, push the newly entered element's pair onto the heap; before reading off the current window's maximum, pop and discard any pairs from the top of the heap whose index has fallen outside the current window (lazy deletion, since a heap can't efficiently remove an arbitrary interior element). This avoids rescanning all k elements per window by reusing the heap across windows, at the cost of extra memory for entries that are pushed but later discarded. Time: O(n log n) Space: O(n)

Maintain a deque of indices whose corresponding values are kept in strictly decreasing order from front to back. For each new element, pop indices from the back whose values are smaller than the current one (they can never be the maximum of any future window that also contains the current element), then push the current index; also pop the front index if it has fallen outside the current window. The front of the deque is always the maximum of the current window. Each index is pushed and popped at most once, giving strictly linear time with much less memory than the heap approach. Time: O(n) Space: O(k)

For every position where a window of size k fits, scan all k elements inside it to find the maximum, then slide the window over by one and repeat from scratch. This directly implements the problem's definition and is trivially correct, but it recomputes the maximum of largely overlapping windows independently every time. Time: O(n*k) Space: O(1)

1. Maintain a max-heap of (value, index) pairs representing candidates for the current window's maximum. 2. As the window slides one step to the right, push the newly-entered element's (value, index) pair. 3. Before reading off the current maximum, lazily pop any heap-top entries whose index has fallen OUTSIDE the current window (rather than eagerly removing them the moment they leave) - the first entry remaining at the top with a valid index is the window's true maximum.

Time: O(n log n) with the heap-based lazy-deletion approach; an alternative deque-based approach (keeping indices in decreasing order of value) achieves an even better O(n), since a deque avoids the log factor entirely. Space: O(n) in the worst case, for the heap (or the deque in the alternative approach).

k = 1 (output equals the input array), k = n (a single output, the global maximum), and n = 10^5 for performance.

Be ready to also present the DEQUE-based O(n) solution as an improvement over the heap-based O(n log n) one - a monotonic deque (keeping indices whose values are in decreasing order, discarding smaller ones from the back as bigger ones arrive) is the more elegant, optimal solution for this specific problem.