Welcome to our next lesson. In our previous session, we dissected the 'Trapping Rainwater' problem, progressing from a straightforward brute-force method to an elegant two-pointer solution. This journey highlighted how identifying and removing computational redundancies can lead to significant performance gains, a core skill in algorithm design.
Today, we'll apply this same progressive optimization mindset to another classic and highly-frequently asked interview problem: 'Sliding Window Maximum'. You'll be given an array and a window of a fixed size k that slides across it. Your task is to find the maximum value within that window at each position. This lesson will not only introduce a powerful use case for the Deque (Double-Ended Queue) data structure but will also reinforce the pattern of building from a simple idea to a highly efficient, linear-time algorithm.
1. Understanding the Problem
Imagine you have a long sequence of numbers and a small viewport of size k through which you can only see k numbers at a time. As this viewport slides one position to the right, your goal is to report the largest number you see at every step.
Let's start by looking at the formal problem statement to solidify our understanding.
Sliding Window Maximum - Tutorial
This article from takeUforward, the source you prefer for our course, clearly defines the problem and provides an illustrative example.
Please read the problem statement and review the detailed example under "Examples". This will help you visualize how the output is generated as the window moves.
2. The Brute-Force Approach: O(n*k)
Following our established pattern, let's start with the most intuitive solution. For each possible starting position of the window, we can simply iterate through the k elements inside it and find the maximum.
The algorithm would be:
- Create a result list.
- Loop from the first possible window start
i = 0to the last possible starti = n - k. - For each
i, create an inner loop that runs fromj = itoj = i + k - 1. - In this inner loop, find the maximum value.
- Add this maximum value to the result list.
- Return the result list.
This approach is correct, but let's analyze its efficiency.
Sliding Window Maximum - Tutorial
The takeUforward article provides a clean walkthrough of this naive method, including the algorithm and Java code.
First, read the brief description under "Algorithm". Then, study the provided Java code to see how the nested loops are implemented. Finally, take note of the complexity analysis. The O(n*k) time complexity is the key takeaway here; it's what we need to improve.
The O(n*k) complexity arises from re-scanning the window at every step. As you can imagine, for large arrays and window sizes, this will be too slow. The core inefficiency is that we are re-calculating the maximum from scratch each time, even though consecutive windows share k-1 elements. How can we avoid this redundant work?
3. An Optimal Solution with a Deque
The bottleneck is finding the maximum in O(k) time for each window. To achieve a linear-time solution, we need to get this down to O(1) amortized time. This is where a specialized data structure, the Deque (Double-Ended Queue), comes into play.
A Deque is a queue that allows you to add or remove elements from both the front and the back. In Java, this is commonly implemented using java.util.ArrayDeque. We will use it to maintain a list of "useful" candidate indices from the current window.
The Core Logic:
We will create a Deque that stores the indices of elements in the current window. We will maintain a special property: the indices in the Deque will correspond to elements in the original array that are in decreasing order. This ensures that the index at the front of the Deque always corresponds to the largest element in the current window.
Let's break down the process as we iterate through the array with index i:
- Clean up the front: Before processing the element
arr[i], we check the index at the front of the Deque. If it's outside our current window (i.e.,deque.peekFirst() <= i - k), we remove it. It's an old index we no longer care about. - Clean up the back: Now, we look at the new element
arr[i]. We compare it with the elements corresponding to the indices at the back of the Deque. Ifarr[i]is greater, it means those smaller elements at the back can never be the maximum again as long asarr[i]is in the window. So, we remove their indices from the back until this condition is no longer true. - Add the new index: After cleaning up, we add the current index
ito the back of the Deque. - Get the maximum: If our window is fully formed (i.e.,
i >= k - 1), the maximum for this window is simply the element at the index at the front of the Deque:arr[deque.peekFirst()]. We add this to our results.
This process ensures that for each window, we can find the maximum in O(1) time by just looking at the front of the Deque. While the inner "clean up the back" loop might seem expensive, each element is added and removed from the Deque at most once over the entire traversal, leading to an amortized O(1) cost per step.
Let's watch a video that walks through this logic with a clear example.
Sliding Window Maximum | Leetcode
This video from the take U forward channel provides an excellent, step-by-step dry run of the Deque-based approach. It masterfully explains the intuition behind each operation.
Please watch the main explanation from the optimal approach section. Pay close attention to these key moments: The introduction of the Deque and why we store indices. The logic for removing smaller elements from the back (pop_back). The logic for removing out-of-boundary elements from the front (pop_front). How the front of the Deque always holds the index of the window's maximum.
Here is a static image that also visualizes the state of the array and the Deque at each step.
Now that you have a solid grasp of the intuition, let's examine a clean Java implementation of this optimal algorithm.
Sliding Window Maximum (Maximum of all subarrays ...
This GeeksforGeeks article provides a well-structured explanation and a clean Java implementation of the Deque-based solution.
Read the section titled "[Expected Approach] - Using Deque" to review the algorithm steps. Then, carefully study the Java code block. Trace how it implements the three key operations: removing out-of-bound indices, removing smaller elements from the back, and adding the new index. Finally, review the complexity analysis, which confirms the O(n) time and O(k) space efficiency.
Conclusion
In this lesson, we tackled the 'Sliding Window Maximum' problem, a staple of technical interviews. We saw how a naive brute-force approach leads to an inefficient O(n*k) solution. By thinking critically about the redundant work, we arrived at an optimal linear-time solution using a Deque.
Key Takeaways:
- The brute-force method involves re-scanning each window, resulting in O(n*k) time complexity.
- The optimal solution uses a Deque to maintain a monotonically decreasing sequence of indices of potential maximums.
- This structure allows us to find the maximum for each window in amortized O(1) time by simply peeking at the front of the Deque.
- The overall time complexity is O(n) because each element is enqueued and dequeued at most once. The space complexity is O(k) for storing the Deque.
This lesson concludes our module on Stacks and Queues. You've seen how these seemingly simple data structures can be used in clever ways (monotonic stacks, deques for windowing) to solve complex problems efficiently.
In our next module, we will shift gears and enter the world of Backtracking. This is a powerful, generalized recursive technique used to solve problems that involve exploring many possible solutions, such as generating permutations, solving Sudoku, or navigating a maze.