Monotonic Stack for Next Greater Element

Recommended resources

The freely available resources this lesson will direct you to.

Hello! Welcome to your next lesson in the "Advanced Algorithmic Patterns" module.

In our last session, we explored how to use binary search on a monotonic answer space to efficiently solve optimization problems. We saw that by identifying a monotonic property in the potential answers, we could transform a slow linear search into a fast logarithmic one.

Today, we'll dive into another powerful pattern that uses a specific data structure to achieve linear-time performance: the monotonic stack. This technique is the go-to solution for a class of problems centered around finding the "next greater" or "next smaller" element in a sequence. This pattern is not only a common interview question but also has applications in areas like signal processing and time-series data analysis.

1. The "Next Greater Element" Problem

Let's start by defining the core problem. Given an array of numbers, we want to find the next greater element (NGE) for each element. The NGE for an element x is the first element to its right that is greater than x. If no such element exists, the NGE is considered to be -1.

Example: For the array [4, 5, 2, 10]:

The NGE of 4 is 5.
The NGE of 5 is 10.
The NGE of 2 is 10.
The NGE of 10 is -1 (no element to its right).

The result would be [5, 10, 10, -1].

The Brute-Force Approach

The most intuitive solution is to use nested loops. For each element, we scan all the elements to its right to find the first one that is greater.

L5. Next Greater Element | Stack and Queue Playlist

To appreciate the efficiency of the monotonic stack, let's first understand the baseline brute-force solution. This video from 'take U forward' clearly explains this initial thought process.

Watch from 02:19 to 04:17. This section walks through the O(N^2) nested loop approach and discusses its time and space complexity. This sets the stage for why we need a more optimal solution.

This O(N^2) approach is simple but inefficient for large inputs, which are common in interview settings and real-world applications. This performance bottleneck is our cue to look for a more specialized, linear-time solution.

2. Introducing the Monotonic Stack

A monotonic stack is a stack that maintains its elements in a strictly increasing or decreasing order. This property is enforced by controlling how elements are pushed onto the stack.

Monotonically Increasing Stack: When pushing a new element, we pop all elements from the top of the stack that are greater than the new element.
Monotonically Decreasing Stack: When pushing a new element, we pop all elements from the top of the stack that are smaller than the new element.

Monotonic Stack Explained

Before we apply it, let's get a clear definition of what a monotonic stack is. This short video from Kacy Codes provides a concise and clear explanation of the concept.

Watch from the beginning to 02:13. This part defines both increasing and decreasing monotonic stacks and walks through the push/pop logic to maintain the monotonic property.

So, how does this help us find the Next Greater Element in O(N) time? The key insight is to process the input array in reverse.

Monotonic Stack Visualization for Next Greater Element — This diagram shows how a monotonic stack's contents change as we process an array. For each new element, we pop smaller elements from the stack before pushing the new one, maintaining the monotonic property.

Let's watch a detailed walkthrough that brings this idea to life.

L5. Next Greater Element | Stack and Queue Playlist

The 'take U forward' video provides an excellent intuition using a 'light pole' analogy and then provides a step-by-step walkthrough of the optimized algorithm.

Watch from 04:33 to 12:47. Pay close attention to: The Intuition (04:33 - 05:57): Why traversing from right-to-left is beneficial. The Walkthrough (05:57 - 12:47): How the stack is used to find the NGE for each element. Notice when and why elements are popped. The smaller elements are discarded because the current, larger element 'blocks' them from being the NGE for any elements to the left.

The logic is as follows: as we iterate from right to left, the stack will hold elements we've already seen (which are to the right of our current element). Because we maintain it as a monotonically decreasing stack:

We pop all elements from the stack that are less than or equal to the current element. These can't be the NGE for the current element, nor for any element further to the left (because our current element is closer and larger).
After popping, if the stack is not empty, the element at the top is the first one to the right that is greater than our current element—it's the NGE!
We push the current element onto the stack. It now becomes a candidate NGE for the elements we will process next (to the left).

Each element is pushed onto the stack once and popped at most once, leading to an amortized O(1) operation for each element in the array, giving a total time complexity of O(N).

3. A Practical Variant: Daily Temperatures

Let's apply this pattern to a classic interview problem, "Daily Temperatures," which is a slight variation of NGE. Instead of the value of the next greater element, it asks for the number of days you have to wait for a warmer temperature.

This means we need to find the distance (difference in indices) to the next greater element. To do this, we can store pairs of (temperature, index) on the stack, or just store the indices and look up the temperatures in the original array.

739. Daily Temperatures - Solution & Explanation

The NeetCode solution for 'Daily Temperatures' is a perfect resource. It provides a clear explanation, code in multiple languages (including Python and Rust), and a section on common pitfalls.

First, read section '2. Stack' to understand the intuition and the algorithm for solving this problem. Study the Python implementation provided. \nThen, since you're proficient in Rust, take a look at the Rust implementation. Notice the structural similarity to the Python version—the core logic of the while loop and stack manipulation is identical. This helps map the pattern across languages. \nFinally, carefully read section '3. Common Pitfalls'. These points are crucial for writing robust, production-quality code and avoiding subtle bugs during an interview.

The key takeaway is that the fundamental monotonic stack pattern remains the same; we just adapt what we store on the stack and what we calculate when an element is popped to fit the problem's specific requirements.

4. Handling a Circular Array

A common way interview problems add a layer of complexity is by introducing constraints like a circular array. In "Next Greater Element II," the search for a greater element wraps around from the end to the beginning of the array.

How can we adapt our monotonic stack pattern for this? A simple and elegant trick is to iterate through the array twice. By conceptually concatenating the array to itself (e.g., [1, 2, 3] becomes [1, 2, 3, 1, 2, 3]), we allow every element to "see" all other elements as potential next greater elements. In practice, we don't need to create a new array; we can simulate this with clever indexing using the modulo operator.

503. Next Greater Element II - In-Depth Explanation

The AlgoMonster explanation for 'Next Greater Element II' breaks down this circular array variant very effectively.

Read the 'Intuition' and 'Solution Approach' sections to understand the logic. Then, review the Python 'Solution Implementation'. Focus on how the loop for i in range(n * 2 - 1, -1, -1) and the modulo operator i % n are used to simulate the double traversal.

This demonstrates the flexibility of the monotonic stack pattern. By slightly modifying the traversal strategy, we can handle more complex constraints without changing the core push/pop logic of the stack itself.

Conclusion

You've now learned how to use the monotonic stack pattern to solve "next greater element" style problems in linear time, a significant improvement over the naive quadratic approach.

Key Takeaways:

Monotonic Stack: A stack that maintains its elements in a sorted (increasing or decreasing) order. It's a powerful tool for problems involving finding the next/previous greater/smaller element.
Core Logic: The pattern usually involves iterating through the array (forwards or backwards) and using the stack to maintain a set of "candidate" answers. Elements that no longer fit the monotonic property are popped, as they are no longer viable candidates for future elements.
O(N) Complexity: Each element is pushed and popped at most once, resulting in an efficient O(N) time complexity. The space complexity is also O(N) for the stack in the worst case.
Adaptability: The basic pattern can be adapted to solve variations, such as finding the distance to the next greater element or handling circular arrays.

How to Identify a Monotonic Problem Flowchart — This flowchart is a great mental model. It shows that for problems involving 'Next Greater/Smaller' elements where expiry isn't a factor (we only care about what's to the right, not a fixed window), a Monotonic Stack is the right tool.

Next Lesson Preview

The flowchart above also hints at what's next. What if elements do expire? For problems like finding the maximum or minimum value in every sliding window of an array, we need a data structure that allows efficient removal from both ends. In our next lesson, we will build upon today's concepts to solve sliding window minimum/maximum problems in linear time using a monotonic queue (deque).