Monotonic Queue

Opening scenario

Sliding Window Maximum (LC 239): given nums and a window size k, return an array where position i is the maximum of nums[i:i+k] — the max of every contiguous window of length k as it slides left to right.

LC numbers identify LeetCode problems.

Assume nums is nonempty and 1 <= k <= len(nums). When a new value enters, which older values can no longer become a window maximum before they leave?

Question progression

Q1 — Recomputing each window's max is O(nk). What is being wasted?

Question: The obvious solution recomputes max(nums[i:i+k]) for every window — O(nk). Two adjacent windows overlap in k-1 elements. What information from the previous window can you carry forward instead of rescanning?

Reasoning: When the window slides by one, exactly one element enters (on the right) and one leaves (on the left). Re-scanning the k-1 shared elements is…