Welcome to our next lesson on stacks. In our previous session, we mastered the 'Valid Parentheses' problem, using the stack's LIFO property to elegantly solve it. We also established that Java's Deque interface, implemented by ArrayDeque, is the modern and robust choice for stack operations.
Today, we'll build on that foundation to explore a powerful and widely applicable pattern: the monotonic stack. This is a specialized use of a stack that is key to solving a category of problems that seem complex at first glance. Our goal for this lesson is to apply this pattern to find the 'Next Greater Element' (NGE) for every element in an array. As per your preference, we will begin with a straightforward brute-force solution before developing the highly efficient monotonic stack approach, preparing you for a common FAANG-level interview pattern.
1. Understanding the 'Next Greater Element' Problem
The problem is simple to state but requires a clever solution to be efficient. Given an array of numbers, your task is to find the next greater element for each element. The next greater element for a number x is the first number to its right that is strictly greater than x. If no such element exists (i.e., all elements to the right are smaller or equal), the next greater element is considered -1.
Let's look at an example to make this clear.Input: arr = [1, 3, 2, 4]Output: [3, 4, 4, -1]
- For
1, the first element to its right that is greater is3. - For
3, we skip2and find4. - For
2, the next element is4, which is greater. - For
4, there are no elements to its right, so its NGE is-1.
To formalize this, please read the problem description from the "takeUforward" guide, which is based on Striver's DSA sheet.
Next Greater Element Using Stack - Tutorial
This article clearly defines the problem with well-explained examples.
Read the problem statement and the examples. This will solidify your understanding of what needs to be calculated for each element in the input array.
2. The Brute-Force Solution: O(n²)
Following our learning path, let's start with the most intuitive approach. For each element in the array, we can simply scan all the elements to its right. The first one we find that is larger is our answer for that element.
This logic translates directly into a nested loop structure.
L5. Next Greater Element | Stack and Queue Playlist
In this clip from the 'take U forward' channel, Striver outlines the logic for the brute-force approach.
Watch the initial explanation of the problem and the development of the nested loop solution. Pay attention to the reasoning behind the O(n^2) time complexity.
The brute-force method is easy to conceptualize and implement. For a detailed code example in Java, you can refer to the GeeksforGeeks article.
This resource provides a clear explanation and a Java implementation of the brute-force method.
Read the section titled "Naive Approach". Focus on how the two nested loops correspond to the "for each element, look to the right" logic. This O(n^2) solution is a good baseline, but for large arrays, it will be too slow for an interview setting.
3. The Optimal Solution: The Monotonic Stack Pattern
To optimize from O(n^2), we need to avoid repeatedly scanning the array. This is where the monotonic stack comes in.
First, what is a monotonic stack?
Monotonic Stack in 6 minutes | LeetCode Pattern
This short video from AlgoMasterIO gives a concise definition of the monotonic stack pattern.
Watch the first minute of the video to understand the core concept. A monotonic stack is simply a stack that maintains its elements in a specific order, either always increasing or always decreasing. For our NGE problem, we will be using a monotonic decreasing stack.
The key insight for solving the NGE problem efficiently is to process the array from right to left. Why? Because when we are at an element arr[i], we have already processed all the elements to its right, and this is exactly the information we need to find its NGE.
L5. Next Greater Element | Stack and Queue Playlist
Striver explains the crucial intuition behind traversing the array backward.
Watch this segment from "if you Traverse from the back" to understand why a right-to-left traversal is the natural fit for this problem.
With this backward traversal in mind, we can now formulate the monotonic stack algorithm:
- Initialize an empty stack (we'll use
Deque<Integer> stack = new ArrayDeque<>();) and a result array. - Iterate through the input array from the last element to the first (
i = n-1down to0). - For each element
arr[i]:
a. Look at the elements currently in the stack. While the stack is not empty and the element at the top of the stack is less than or equal toarr[i], pop it. Why? Because ifarr[i]is greater than the stack's top element, that top element can never be the NGE forarr[i]or any other element to the left ofarr[i](sincearr[i]is a closer and greater element).
b. After the popping loop, what remains at the top of the stack is the first element to the right ofarr[i]that is greater than it.
* If the stack is now empty, it means there is no greater element to the right. The NGE forarr[i]is-1.
* Otherwise, the NGE forarr[i]is the element atstack.peek().
c. Finally, push the current elementarr[i]onto the stack. This maintains the monotonic (decreasing) property and makesarr[i]available for comparison by elements to its left.
Let's watch a detailed walkthrough of this algorithm. Striver's "light pole" analogy is an excellent way to build intuition.
L5. Next Greater Element | Stack and Queue Playlist
This is the core of the lesson, where the monotonic stack algorithm is explained in detail with a visual analogy.
Watch the full explanation from the start of the stack traversal. The key moment is when he explains why you pop smaller elements: they are "blocked" by the current, taller "light pole" and thus become irrelevant for future elements to the left.
Here is a static visualization of the process for the array [1, 3, 4, 2]. The algorithm processes from right to left (bottom to top in the image).
4. Java Implementation and Complexity Analysis
Now, let's translate this algorithm into clean Java code. The implementation in the "takeUforward" article is a perfect reference. It uses java.util.Stack, but remember from our last lesson that Deque is the preferred interface. The methods (push, pop, peek, isEmpty) are the same.
Next Greater Element Using Stack - Tutorial
This resource provides the complete Java code for the optimal solution.
Review the Solution class code. Trace its logic against the algorithm we just discussed. Notice the right-to-left loop, the while loop for popping, the check for an empty stack, and the final push.
A common question is: with a for loop and a while loop, isn't the complexity still O(n^2)? The answer is no, and the reason is crucial. Each element from the input array is pushed onto the stack exactly once and popped from the stack at most once.
L5. Next Greater Element | Stack and Queue Playlist
Striver provides an excellent explanation of the amortized time complexity.
Watch the segment on complexity analysis from "time to analyze the time complexity". The key takeaway is that the total number of pop operations across all iterations of the outer loop is at most n. Therefore, the total work is O(n) + O(n), which simplifies to O(n).
Complexity Analysis Summary:
- Time Complexity: O(n). We iterate through the array once. Although there's a nested
whileloop, each element is pushed and popped at most once over the entire execution, leading to a linear time complexity. This is often referred to as amortized O(1) time for the inner loop operations. - Space Complexity: O(n). In the worst-case scenario (e.g., an array sorted in decreasing order like
[5, 4, 3, 2, 1]), the stack will hold allnelements.
Conclusion
In this lesson, you've moved beyond basic stack usage to a more advanced and powerful interview pattern: the monotonic stack. You've seen how to identify a problem that fits this pattern and how to progress from a simple brute-force approach to an elegant and efficient O(n) solution.
Key Takeaways:
- The Next Greater Element problem asks for the first element to the right that is strictly greater.
- The brute-force solution uses nested loops and has a time complexity of
O(n^2). - A monotonic stack maintains its elements in a sorted order (either increasing or decreasing).
- The optimal solution uses a right-to-left traversal and a monotonic decreasing stack.
- The core logic involves popping elements from the stack that are smaller than or equal to the current element, as they are "obstructed" and can no longer be the NGE for any future elements to the left.
- The time complexity is
O(n)because each element is pushed and popped at most once.
This pattern is a fundamental building block. In our next lesson, we will tackle a more challenging problem, 'Largest Rectangle in a Histogram,' which is a classic and direct application of the monotonic stack pattern you've learned today.