Sliding Window Maximum Using a Deque

Given an array of N integers and a window size K, consider every contiguous window of K consecutive elements as it slides from the start of the array to the end (there are N-K+1 such windows). For each window, report the maximum value it contains. Solve this efficiently using a double-ended queue (deque) that stores candidate indices rather than recomputing the maximum from scratch for every window.

Input: The first line contains two integers N and K. The second line contains N space-separated integers, the array. Output: Print the N-K+1 window maximums, in order, separated by single spaces on one line.

1 <= K <= N <= 100000, -10^9 <= arr[i] <= 10^9

A DEQUE (not a plain queue or stack) is essential here specifically because pruning needs to happen from BOTH ends - the back (removing now-irrelevant smaller values) and the front (removing now-out-of-window values) - a capability only a double-ended structure provides efficiently.

For every sliding window of a fixed size across an array, efficiently find each window's maximum value using a double-ended queue. 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: Maintaining the deque in strictly DECREASING value order means the FRONT is always the current maximum candidate, and popping stale/beaten values (from either end) ensures every element is pushed and popped from the deque AT MOST ONCE across the whole algorithm - giving true O(N) total work despite processing N windows.

1. Maintain a deque of INDICES, keeping their VALUES strictly decreasing from front to back. 2. Before pushing a new index onto the back, pop every index from the back whose value is <= the new value - those can never be the maximum again, since the new value is both bigger AND more recent. 3. Before reading the current window's maximum, pop any index from the FRONT that has slid outside the window's left boundary; the front of the deque is always the current window's maximum.

Time: O(N) - each element enters and leaves the deque at most once. Space: O(K) in the worst case, for the deque holding at most K candidate indices.

When K = N there is exactly one window and one output value (the overall maximum); when K = 1 the output is identical to the input array.

Be ready to explain BOTH pruning rules clearly: popping from the BACK when a new value beats older candidates, and popping from the FRONT when a candidate slides out of the window's range - both are essential and serve different purposes.