Sliding Window Maximum with Deque

The Problem: Sliding Window Maximum

Imagine you have an array of numbers and a window of a fixed size k. This window slides from the very left of the array to the very right, one position at a time. For each position of the window, you need to find the maximum element inside it.

Let's take an example: nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3.

The process would look like this:

• [1, 3, -1] -3, 5, 3, 6, 7 (Max is 3)
• 1, [3, -1, -3] 5, 3, 6, 7 (Max is 3)
• 1, 3, [-1, -3, 5] 3, 6, 7 (Max is 5)
• ...and so on.

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

1. The Brute-Force Approach

The most straightforward solution is to simply follow the problem description. You can iterate through each possible starting position of the window and then loop through the k elements within that window to find the maximum.

This approach involves a nested loop structure, which gives it a time complexity of O(N * k), where N is the number of elements in the array. While this works for small inputs, it's too slow for the constraints typical in competitive programming and interviews (e.g., N up to 10^5).

To see this explained, watch the beginning of the following video.

2. Towards an Optimal Solution: Why Not a Heap?

Your first instinct to optimize might be to use a data structure designed for finding maximums quickly, like a max-heap (PriorityQueue in Java). You could maintain a heap of the k elements in the window. The maximum would always be at the root, accessible in O(1).

However, when the window slides, you must remove the element that falls out of the window's left boundary. Removing an arbitrary element from a heap is an O(k) operation, which brings us back to an O(N*k) total complexity. A slightly more clever approach involves not removing elements immediately, but only checking if the root of the heap is outdated. This improves the complexity to O(N log k). While better, we can still do one better!

The key insight is that we are doing redundant work. We don't need to keep all k elements to know the maximum. We only need to keep track of the potential candidates for the maximum.

3. The Optimal Solution: The Monotonic Deque

This is where the deque shines. We will use a deque to store the indices of elements in the current window. The crucial idea is to maintain a monotonically decreasing sequence of elements in the deque. This means the element at the front of the deque is always the largest, the next one is the second largest of the remaining, and so on.

By storing indices instead of values, we can do two things:

1. Access the element's value using nums[index].
2. Know if an element is out of the current window's bounds.

To maintain this "monotonic deque," we follow three simple rules as we iterate through the array from left to right with an index i:

1. Clean the Front: Before processing nums[i], look at the index at the front of the deque. If this index is outside the current window (i.e., deque.front() <= i - k), it's no longer relevant, so remove it from the front (pollFirst()).

2. Clean the Back: Now, look at the element nums[i]. We need to add its index i to the deque, but first, we must maintain the decreasing property. While the deque is not empty and the element corresponding to the index at the back is smaller than nums[i], remove that index from the back (pollLast()). Why? Because if nums[i] is larger, the smaller element at the back can never be a maximum in any future window that includes nums[i]. It has become useless.

3. Add to Back: Add the current index i to the back of the deque (offerLast()).

After these steps, the index at the front of the deque always corresponds to the maximum element in the current window. Once our window is fully formed (i >= k - 1), we can add nums[deque.peekFirst()] to our result list.

The following video provides an excellent animated walkthrough of this logic.

Here is a static image that also walks through the process, which you can use as a reference.

4. Implementation and Complexity Analysis

Now, let's put this into code and analyze its efficiency.

Time Complexity: O(N)

You might think the nested while loop inside the for loop makes the complexity worse than O(N). However, we can use amortized analysis. Each element's index is pushed onto the deque exactly once. It is also popped from the deque at most once. Therefore, over the entire algorithm, every element results in a constant number of deque operations. This leads to a total time complexity of O(N).

Space Complexity: O(k)

In the worst case (a strictly decreasing array), the deque will hold k indices at a time. Therefore, the space complexity is O(k).

For a deeper dive into the concept, sometimes called a "Monotonic Queue," and its implementation as a class (a very clean software engineering practice), you can explore this resource.

Conclusion

Congratulations! You've just learned how to solve a challenging and common interview problem using a deque in the most optimal way. This technique of using a deque to maintain a monotonic (either increasing or decreasing) sequence of candidates is a powerful pattern that can be applied to other problems as well.

Key Takeaways:

• The brute-force solution for Sliding Window Maximum is O(N*k).
• A heap-based solution improves this to O(N log k) but is still not optimal.
• The optimal solution uses a deque to maintain a list of indices whose corresponding values are monotonically decreasing.
• This "monotonic deque" allows you to find the maximum in each window in amortized O(1) time, leading to an overall O(N) time complexity and O(k) space complexity.

Preview of the next lesson:
We'll now switch gears back to stacks. In the next lesson, you will learn how to solve another set of classic computer science problems: converting an infix expression to postfix (Reverse Polish Notation) and evaluating it using a stack. This is a fundamental concept in compiler design and expression parsing.