Sliding Window Deque for Max/Min

Hello! Welcome to our next lesson.

In our last few lessons, we've explored the sliding window pattern, focusing on how to use frequency maps to manage variable-size and fixed-size windows for substring problems. You mastered techniques for finding anagrams and solving the complex "Minimum Window Substring" problem.

Today, we're tackling a different kind of challenge within a fixed-size window. Instead of counting characters, our goal is to find the maximum (or minimum) value in each window as it slides across an array. This is a classic problem that comes up frequently in interviews, typified by LeetCode 239: "Sliding Window Maximum".

Sliding Window Maximum Illustration — This image shows a window of size 3 sliding across an array. For each position, the maximum element inside that window is identified, and these maximums form the final output array.

The brute-force approach of re-scanning each window is too slow for competitive programming and interview constraints. Our learning outcome for today is to apply the sliding window deque method to find maximums or minimums in a fixed-size window in optimal linear time. This specialized data structure, the monotonic deque, is the key to an O(n) solution.

1. The Problem with the Naive Approach

First, let's understand why a more clever solution is necessary. The most straightforward approach is to iterate through the array, and for each starting position of the window, loop through the next k elements to find the maximum.

This approach is simple to conceptualize but has a significant performance drawback. To see why, let's watch a quick explanation.

L16. Sliding Window Maximum | Stack and Queue Playlist

The video 'Sliding Window Maximum' by take U forward begins by clearly defining the problem and then analyzes the brute-force solution.

Watch from the beginning to 04:52. The video explains the brute-force method and calculates its time complexity, O(n*k), highlighting why this is insufficient for typical interview constraints.

As the video explains, a time complexity of O(n * k) is often too slow. If an array nums has 100,000 elements and the window size k is also large, the number of operations can run into the billions, leading to a "Time Limit Exceeded" error. This signals that we need a linear time, O(n), solution.

The inefficiency comes from redundant work. As the window slides, we re-evaluate many of the same elements over and over. The key to optimization is to avoid this repeated scanning.

2. The Core Insight: A Monotonically Decreasing Queue

To achieve O(n) complexity, we need to find the maximum in each window in constant time, O(1). How can we do this?

The breakthrough idea is that we don't need to store every element in the window. Consider a window containing [... 8, 3, 5 ...]. Once we see the 8, the 3 that came before it is essentially "useless" for the purpose of finding a future maximum. As long as the 8 remains in the window, the 3 can never be the max. However, the 5 that comes after 8 is still potentially useful, as it might become the maximum once 8 slides out of the window.

This leads us to a powerful data structure: a monotonic deque (double-ended queue). We'll use it to store the indices of elements from the current window, with a special rule: the values corresponding to these indices will always be in strictly decreasing order.

Sliding Window Maximum - Monotonic Queue - Leetcode 239

The video 'Sliding Window Maximum' from NeetCode provides an excellent explanation of this core concept—why we can discard smaller elements and how this leads to the idea of a monotonic queue.

Please watch from 02:16 to 04:58. Focus on the logic of why certain elements become irrelevant once a larger element appears. This is the fundamental principle behind the optimized approach.

By maintaining this decreasing order, the index of the largest element in the current window will always be at the front of the deque. This gives us O(1) access to the maximum at any time.

3. The Monotonic Deque Algorithm

A deque is the perfect data structure because we need to:

Add new elements to the back.
Remove useless smaller elements from the back.
Remove elements that slide out of the window from the front.

Here is the complete algorithm as we iterate through the array with index i from 0 to n-1:

Clean the Deque (from the back): Before adding the new element's index, check the back of the deque. While the deque is not empty and the value of the new element nums[i] is greater than or equal to the value at the index at the back of the deque (nums[deque.back()]), pop from the back. This removes all the "useless" smaller elements that can no longer be the maximum.
Add the New Element's Index: Push the current index i to the back of the deque.
Clean the Deque (from the front): Check the index at the front of the deque. If it is outside the current window's bounds (i.e., deque.front() <= i - k), pop it from the front.
Record the Result: If the window is fully formed (i.e., i >= k - 1), the maximum for this window is the element at the index at the front of the deque (nums[deque.front()]). Add this value to our result list.

Let's watch a detailed dry run to see these rules in action.

L16. Sliding Window Maximum | Stack and Queue Playlist

The 'take U forward' video provides a methodical, step-by-step dry run of the deque algorithm, making it very clear how the deque's state changes with each new element.

Watch from 09:28 to 14:51. Pay close attention to how the three rules (clean back, clean front, add back) are applied at each step and how the front of the deque always points to the window's maximum.

Here's another visual summary of the process:

Sliding Window Maximum using Deque — This image illustrates the state of the deque as the sliding window moves across the array, showing how elements are added and removed to maintain the decreasing property and identify the maximum.

Test your understanding!

Let nums = [1, 3, -1, -3, 5] and k = 3. The deque is currently [1, 2] (pointing to values 3 and -1). We are about to process the element at index 3, which is -3.

What is the state of the deque after processing index 3?

Show answer

Clean the Back: The new element is -3. The element at the back of the deque is nums[2], which is -1. Since -3 is not greater than -1, we do not pop from the back.
Add to Back: We add the new index 3 to the back. The deque is now [1, 2, 3].
Clean the Front: The current index i is 3. The window is [1, 2, 3]. The index at the front is 1, which is not out of bounds (1 is not <= i - k, which is 3 - 3 = 0). So, we don't pop from the front.
Record Result: The window is full (i=3 >= k-1=2). The max is nums[deque.front()] which is nums[1] = 3.

The final state of the deque after processing index 3 is [1, 2, 3].

4. Implementation, Complexity, and Pitfalls

With a solid grasp of the algorithm, let's turn to implementation. One of the most common mistakes is storing values in the deque instead of indices. Storing indices is crucial for knowing when an element has slid out of the window.

This guide provides a fantastic, interview-oriented breakdown of the solution, including well-commented code and a discussion of common pitfalls and edge cases.

LC239: Sliding Window Maximum Solution Guide

This guide from Sanjay Patidar is a deep dive into the Sliding Window Maximum problem, tailored for interview preparation.

Please read the following sections: javascript.optimized.js (and Python if you like): Review the commented code. The comments are rich with interview tips, explaining the 'why' behind each line. Common Pitfalls: Pay close attention to this section. It highlights frequent mistakes like storing values instead of indices. Time & Space Complexity: Understand the O(n) time and O(k) space analysis. This is critical to explain in an interview. FAQs: This section reinforces key concepts and answers questions you might be asked.

Complexity Analysis Summary:

Time Complexity: O(n). This is the optimal solution. Although there is a while loop inside the main for loop, the amortized analysis shows that each element is pushed onto the deque at most once and popped at most once over the entire iteration. Therefore, the total time is linear.
Space Complexity: O(k). In the worst-case scenario (e.g., a strictly decreasing array), the deque could hold up to k indices. In the best-case (e.g., a strictly increasing array), it would hold only one index.

Conclusion

In this lesson, you've added a powerful and specialized tool to your sliding window toolkit: the monotonic deque. This pattern is the go-to solution for finding the maximum or minimum in a fixed-size sliding window efficiently.

Key Takeaways:

The brute-force O(n * k) solution is too slow for typical constraints.
A monotonic deque stores indices of elements, ensuring their corresponding values are in a sorted (decreasing for max, increasing for min) order.
This structure provides O(1) access to the window's maximum (or minimum) at any time.
The algorithm involves three key steps at each iteration: cleaning the back of the deque, adding the new index, and cleaning the front of the deque.
The final solution has an optimal O(n) time complexity and O(k) space complexity.

Preview of the Next Lesson:
We have now concluded our module on core array patterns. Congratulations! We will now move on to the next module: Advanced Searching and Stack Applications. In our next lesson, we will explore a powerful search technique that goes beyond simple sorted arrays: applying binary search on the answer space. This is a non-obvious but highly effective pattern for solving a class of optimization problems, such as "minimize the maximum" or "find the minimum capacity."