Sliding Window Minimum and Maximum

Problem Given an array and a window size m, report the minimum and the maximum element of every contiguous window of size m as the window slides across the array.

Input / Output

• Input: array arr of integers and window size m
• Output: two arrays of length n - m + 1 — the per-window maxima and the per-window minima

Constraints

• 1 <= arr.length <= 10^5, so the O(n*m) rescan and the O(n log m) heap solution are both suboptimal
• 1 <= m <= arr.length
• Values may be negative and may repeat

Example

• arr = [1,3,-1,-3,5,3,6,7], m = 3 → max per window: [3,3,5,5,6,7]; min per window: [-1,-3,-3,-3,3,3]
• Tricky case: a strictly decreasing run like [5,4,3] keeps every element in the max-deque simultaneously — the deque holds m entries, which is the space bound