Sliding Window Extrema with Monotonic Deques

Welcome to the third lesson in our module on high-value interview patterns. In our previous sessions, we explored how to find a single element in an unsorted array with Quickselect and how to efficiently merge multiple sorted sequences using a heap. Today, we turn our attention to another common scenario involving sequences: finding the maximum (or minimum) value within a "sliding window" as it moves across an array.

This lesson will teach you how to use a monotonic deque, a specialized and highly efficient data structure, to solve this problem in linear time. Mastering this pattern is crucial for a specific class of problems that require finding extrema over a moving range, a classic interview favorite.

The "Sliding Window Maximum" Problem

Imagine you have a long array of numbers and a window of a fixed size, say k. This window starts at the very beginning of the array. Your task is to find the maximum number inside the current window. Then, the window slides one position to the right, and you find the maximum again. You repeat this process until the window reaches the end of the array, collecting the maximum from each position.

A straightforward approach would be to iterate through the k elements in each window to find its maximum. Since there are roughly N-k windows in an array of size N, the total time complexity would be about $O((N-k)\times k)$, which simplifies to $O(N\cdot k)$. When N and k are large, this becomes too slow. The inefficiency comes from re-scanning elements that were already checked in the previous window.

The following video quickly explains this brute-force method and why we need a better approach.

As you can see, the key to a faster solution is to avoid redundant work. We need a way to maintain information about the window's potential maximums without having to rescan everything on every slide.

The Insight: Dominance and Candidate Elimination

Let's think about the candidates for the maximum value. Suppose we have two numbers in the window, x and y, where x appears before y. If x <= y, can x ever be the maximum value in any future window that still contains y? The answer is no. Since y is greater than or equal to x and will remain in the window for at least as long as x (and likely longer), x is dominated by y. It's a useless candidate as long as y is around.

This observation is the core of the optimized solution. We can maintain a list of "useful" candidates, discarding any that are dominated by a new, larger element.

This leads us to a specific requirement for our data structure:

1. When a new element enters the window, we need to add it to our candidate list.
2. Before adding it, we must remove any existing candidates from the end of the list that it dominates.
3. When the window slides, the oldest element might fall out. We need to be able to remove it from the front of our candidate list if it's still there.

This set of operations—adding to the back, removing from the back, and removing from the front—points directly to a deque (a double-ended queue).

The Monotonic Deque

To solve this problem efficiently, we will use a deque to store a list of indices of the candidate elements. We maintain a crucial property: the values at these indices will be in strictly decreasing order from the front to the back of the deque. This is why it's called a monotonic deque.

Let's explore the mechanics of this data structure with an excellent article from OneNoughtOne.

By storing indices in a monotonically decreasing order of their corresponding values, we guarantee two things:

1. The index at the front of the deque always corresponds to the maximum element in the current window. We can access it in $O(1)$ time.
2. The deque only contains relevant candidates, making the update process very fast.

The Algorithm Step-by-Step

Let's formalize the algorithm. We will iterate through the input array nums from left to right (from index i = 0 to n-1). For each element nums[i], we perform three steps to maintain our monotonic deque.

1. Remove Expired Indices from the Front

The current window spans from i - k + 1 to i. Any index in our deque that is less than i - k + 1 has expired and is no longer part of the window. Since our deque stores indices in increasing order, we only need to check the front.

2. Remove Dominated Indices from the Back

Now we consider the new element, nums[i]. We look at the index at the back of the deque. If the value at that index is less than or equal to nums[i], it is dominated. We pop it from the back and repeat this check until the deque is empty or the element at the back is greater than nums[i].

3. Add the New Index to the Back

After clearing out the dominated elements, the deque is ready for the new candidate. We push the current index i to the back of the deque.

4. Record the Maximum

If our window is fully formed (i.e., i >= k - 1), the maximum element for this window is simply nums[deque[0]] (the value at the index at the front of the deque). We add this value to our result array.

This video provides a complete, animated walkthrough of this process.

Implementation and Complexity

Let's look at how this translates into code and what pitfalls to avoid.

Complexity Analysis:

• Time Complexity: $O(N)$. This might seem surprising because of the while loops inside the main loop. However, each index from the input array is added to the deque exactly once and removed from the deque exactly once. Therefore, the total number of deque operations is proportional to N, giving us a linear time complexity.
• Space Complexity: $O(k)$. In the worst-case scenario (e.g., an array sorted in descending order), the deque can hold up to k indices at once.

Conclusion

You've now learned a powerful and efficient pattern for solving the Sliding Window Maximum problem. The monotonic deque is a clever application of a simple data structure to maintain a sorted list of candidates, turning a potential $O(N\cdot k)$ problem into a sleek $O(N)$ solution.

Here are the key takeaways:

• The Problem: Finding the maximum (or minimum) in a fixed-size sliding window efficiently.
• The Bottleneck: Brute-force re-scans the window, leading to $O(N\cdot k)$ complexity.
• The Insight: An element x is dominated by a later element y if x <= y. Dominated elements are irrelevant candidates for the maximum.
• The Tool: A monotonic deque that stores indices of candidates, with their corresponding values in decreasing order.
• The Algorithm: For each element, (1) remove expired indices from the front, (2) remove dominated indices from the back, (3) add the current index to the back, and (4) report the front element's value as the window's max.

In our next lesson, we will move into the world of string and prefix-based problems by learning how to build and use a trie. This tree-like data structure is fundamental for tasks like implementing auto-complete features and efficient dictionary lookups.