Monotonic Queue (Sliding Window Max/Min)

Introduction: The “Rolling Maximum” Problem

You are monitoring a live data stream. You need to display the maximum value seen in the last 60 seconds (a sliding window). As every second passes, a new value enters and an old one leaves.

If you search for the max every time, it’s $O(K)$ per step ($K$ is window size). For a window of 1 million points, this is impossible. Monotonic Queue maintains the window in a way that the maximum is always at the front, achieving an amortized $O(1)$ per step.

What Problem does it solve?

• Input: A stream of numbers and a window size $K$.
• Output: The max/min of the current window as it slides forward.
• The Promise: Total processing time of $O(N)$ for the entire stream, regardless of $K$.

Core Idea (Intuition)

Think of a “Survival of the Fittest” queue:

1. When a new value enters: It “challenges” the values already in the queue from the back.
2. If the new value is larger than the value at the back, the old value is useless (it will never be the max as long as the new, larger value is in the window). So, we kick out the smaller old values.
3. The queue remains Monotonically Decreasing (largest at the front).
4. As the window slides, we also check if the front element has “expired” (left the window) and remove it if so.

Why use it?

• ✅ Efficiency: Every element is added once and removed once. Total work is $2N$.
• ✅ Real-time: Perfect for streaming data where you need immediate answers.

Typical Business Scenarios

• ✅ Real-time Charts: Displaying a “High Water Mark” line in a monitoring dashboard.
• ✅ Trading Systems: Calculating the highest bid in the last $N$ ticks.
• ✅ Image Processing: 2D sliding window filters (max-pooling in CNNs).
• ✅ DP Optimization: Many dynamic programming problems can be optimized from $O(N^2)$ to $O(N)$ using a monotonic queue.

Performance & Complexity

• Time: $O(1)$ amortized per element.
• Space: $O(K)$ where $K$ is the window size.

Summary

"A Monotonic Queue is a 'Ruthless Filter'. It kicks out any old value that is smaller than a newer arrival, ensuring that the champion of the window is always sitting at the front."