Sliding Window Maximum with a Monotonic Deque
Problem statement
Given an array $a_1, a_2, \ldots, a_n$ and a window size $W$, output the maximum of each contiguous subarray of length $W$:
$$\text{output}[i] = \max(a_i, a_{i+1}, \ldots, a_{i+W-1}), \quad i = 1, 2, \ldots, n - W + 1$$
Constraints:
- Must run in $O(n)$ time
- Must use $O(W)$ space
Describe the monotonic deque algorithm in detail, then prove that each array index is enqueued and dequeued at most once, establishing the $O(n)$ time bound.
Examples:
Input: a = [1, 3, -1, -3, 5, 3, 6, 7], W = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: Windows are [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7
Input: a = [4, 4, 4, 4], W = 2
Output: [4, 4, 4]
Show hint
Once a newer element is at least as large as an older one, can the older one ever be a window maximum again?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.