Maximum of Every Sliding Window of Size K

Problem Statement

You're processing a real-time stream of metrics (CPU usage, stock prices, sensor readings). You need to efficiently report the maximum value in every consecutive window of size K.

Given an array of n integers and a window size K, return an array of the maximum value in each sliding window as it moves from left to right.

Constraints

• 1 <= n <= 10^5
• 1 <= K <= n
• -10^4 <= nums[i] <= 10^4
• Expected: O(n) time, O(K) space

Example

Input:

nums = [1, 3, -1, -3, 5, 3, 6, 7], K = 3

Output: [3, 3, 5, 5, 6, 7]

Explanation:

Window [1, 3, -1]     → max = 3
Window [3, -1, -3]    → max = 3
Window [-1, -3, 5]    → max = 5
Window [-3, 5, 3]     → max = 5
Window [5, 3, 6]      → max = 6
Window [3, 6, 7]      → max = 7

What the Interviewer Expects

1. Brute force first — O(n*K) nested loop. Acknowledge it's suboptimal.
2. Optimal approach — Monotonic decreasing deque. Explain WHY a deque works (maintains candidates in decreasing order, front is always the current max).
3. Walk through the example — show how elements enter/leave the deque at each step.
4. Edge cases — K=1 (every element is its own max), K=n (single answer: global max), all elements same, strictly increasing, strictly decreasing.

Follow-ups

1. What if the stream is infinite (elements arrive one at a time)? Can you still maintain O(1) per element?
2. How would you modify this to find the minimum of each window? What changes in the deque logic?
3. What if you need both max AND min of each window simultaneously? Can you do it in one pass?
4. What if K is dynamic — it can change between queries? What data structure would you use?
5. How does this relate to the "stock span" problem? Can you see the connection?