Monotonic Queue for Sliding Window Min/Max

Hello! Welcome to your next lesson in the "Advanced Algorithmic Patterns" module.

In our last session, we mastered the monotonic stack, an efficient tool for "next greater element" problems. We saw how maintaining a sorted stack allowed us to find the NGE for every element in linear time. The key was that once we processed an element, it became a candidate for all elements to its left, and it never "expired."

Today, we address a new constraint: what if elements do expire? This is the core challenge in sliding window problems. For example, if we need the maximum of a 3-element window [a, b, c], once the window slides to [b, c, d], element a is no longer relevant. A standard stack can't efficiently remove a from the bottom. This is where the monotonic queue (or deque) comes in. It extends the monotonic principle to handle this "expiration" by allowing efficient removal from both ends.

By the end of this lesson, you will be able to solve sliding window minimum/maximum problems in O(N) time using a monotonic deque, a common and important pattern in technical interviews.

1. The Sliding Window Maximum Problem

First, let's formally define the problem, also known as LeetCode 239. You are given an array of integers nums and a window size k. Your task is to find the maximum value within each contiguous window of size k as it slides from left to right.

Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

• Window 1: [1, 3, -1] -> max is 3
• Window 2: [3, -1, -3] -> max is 3
• Window 3: [-1, -3, 5] -> max is 5
• ...and so on.

The final output would be [3, 3, 5, 5, 6, 7].

The Brute-Force Approach

As with our last problem, the most direct approach is to iterate through each possible window and, for each one, find its maximum element.

An O(N*K) solution is too slow for typical constraints where N can be up to 10⁵. This is our motivation to find a linear-time solution.

2. The Monotonic Deque Solution

The key to an O(N) solution is to efficiently track the maximum element as the window slides, without re-scanning the window every time. We'll use a deque (double-ended queue) to maintain a list of "candidate" indices for the maximum element.

The intuition combines two ideas:

1. Maintaining Monotonicity (Cleaning the Back): Just like with the monotonic stack, if we are considering a new element nums[i], any elements already in our deque that are smaller than nums[i] are now useless. They appeared earlier than nums[i] and are smaller, so they can never be the maximum in any future window that also contains nums[i]. We can pop them from the back of the deque. This ensures our deque always stores indices whose corresponding values are in decreasing order.

2. Handling Expiration (Cleaning the Front): As the window slides to the right, the leftmost element of the previous window might need to be removed. Since we store indices in the deque, we can easily check if the index at the front of the deque has fallen outside the current window's bounds. If it has, we pop it from the front.

By combining these two cleaning steps, the deque always has the index of the current window's maximum element at its front, giving us O(1) access to the max.

Let's watch a detailed walkthrough of this algorithm.

3. Implementation and Complexity

The logic we just saw translates directly into code. The core of the implementation is a loop that iterates through the array, performing the two cleaning operations before adding the current element's index and recording the result.

Algorithm Summary

For each element nums[i]:

1. Clean Front: If the index at deque.front() is out of the window (i.e., deque.front() <= i - k), pop it.
2. Clean Back: While the deque isn't empty and nums[i] is greater than the element at deque.back(), pop from the back.
3. Add: Append the current index i to the back of the deque.
4. Record: If the window is fully formed (i >= k - 1), the max is nums[deque.front()]. Add it to your results.

Let's look at the Python implementation, which uses collections.deque.

Complexity Analysis

• Time Complexity: O(N). Each element's index is added to the deque exactly once and removed at most once. This gives an amortized O(1) cost per element, leading to a linear overall time complexity.
• Space Complexity: O(k). In the worst-case scenario (a strictly decreasing array), the deque could hold up to k indices at one time.

4. Deep Dive: Pattern Recognition and Interview Prep

This problem is a favorite in interviews because it tests your ability to move from a brute-force to an optimal solution using a non-trivial data structure. Understanding the "why" behind the monotonic deque is as important as the "how."

Your experience with high-throughput services like Rudi at AWS gives you a practical appreciation for O(1) amortized operations. The process of evicting out-of-date information (indices outside the window) is conceptually similar to cache eviction or removing timed-out requests from a queue to maintain system performance.

Let's dive deeper into the pattern and how to discuss it in an interview.

A common mistake is storing values in the deque instead of indices. As you saw, indices are essential for knowing when an element has "expired" and left the window.

Since you're proficient in Rust, it's worth noting that the VecDeque in Rust's standard library is a perfect fit for this, providing O(1) pop_front, pop_back, and push_back operations. The fundamental algorithm remains identical across languages.

Conclusion

In this lesson, we've extended the monotonic data structure concept from stacks to deques to handle problems with a sliding window constraint. You can now solve sliding window maximum/minimum problems in optimal linear time.

Key Takeaways:

• Problem: Standard stacks are inefficient for sliding window problems because they don't support fast removal from the front (bottom).
• Solution: A monotonic deque stores indices of candidate maximums. It maintains a strictly decreasing order of values.
• Two-Sided Cleaning:
  • The front is cleaned by removing indices that are out of the window's bounds.
  • The back is cleaned by removing indices of smaller elements when a new, larger element arrives.
• Performance: This approach achieves O(N) time and O(k) space complexity, which is optimal.
• Trade-offs: You can now clearly articulate why a monotonic deque is superior to both the O(N*K) brute-force method and the O(N log k) heap-based method.

Next Lesson Preview

We've now used stacks and deques to find the single greatest element in various contexts. But what if a problem asks for more than just the single max or min? For example, how would you find the "Top K" frequent elements or merge k sorted lists? For these types of problems, we need a data structure that is specifically designed to manage a collection of "top" elements. In the next lesson, we will explore how to solve top-K and 'merge k-sorted lists' problems using heaps (priority queues).