Mastering Monotonic Stacks

The Monotonic Stack: An Ordered Approach

So, what exactly is a monotonic stack? As the name suggests, it's a stack that maintains a strict order among its elements. The elements, from the bottom of the stack to the top, are always sorted, either in a non-increasing (decreasing) or non-decreasing (increasing) fashion.

The core idea is to use this ordered property to efficiently find relationships between elements in a sequence, such as the "next greater element" or "previous smaller element." By processing an array in a single pass and using the stack to keep track of elements "waiting" for their match, we can achieve an optimal time complexity of $O(n)$. This is because each element is pushed onto the stack exactly once and popped at most once.

The following article provides a concise introduction to this concept.

Solving "Next Greater Element"

The "Next Greater Element" problem is the canonical example for demonstrating the power of a monotonic stack. The problem statement is as follows:

Given an array of integers, find the next greater element for each element. The next greater element of x is the first element to its right that is greater than x. If no such element exists, the answer is -1.

For example, given [2, 1, 3, 2, 4, 3], the output should be [3, 3, 4, 4, -1, -1]. A brute-force approach would use nested loops, taking $O(n^2)$ time. We can do much better.

The Algorithm

We will use a monotonically decreasing stack. The stack won't store the numbers themselves, but rather their indices. This is a crucial detail, as it allows us to easily update the corresponding position in our result array.

Here's the plan:

1. Initialize a result array of the same size as the input, filled with -1. This handles the case where no greater element is found.
2. Initialize an empty stack.
3. Iterate through the input array from left to right, with index i and value current_num.
4. For each current_num, we look at the top of the stack. While the stack is not empty and current_num is greater than the number at the index on top of the stack, we have found the "next greater element" for the element corresponding to the index on top of the stack.
   • We pop the index from the stack.
   • We use this popped index to place current_num into our result array.
   • We repeat this until the stack is empty or the condition is no longer met.
5. After the while loop finishes, we push the current index i onto the stack.

This process ensures that the values corresponding to the indices in the stack are always in decreasing order. When we encounter a new number, it "resolves" all the smaller numbers on the stack that were waiting for their next greater element.

The image below shows the initial state for solving this problem. We have our input array, a result array initialized to -1, and an empty stack ready to store indices.

The next image demonstrates the core logic in action. At "step 3," the current element is 3. The top of the stack holds the index for the value 1. Since 3 > 1, we know 3 is the next greater element for 1. We would pop the index for 1 and update our result.

The NeetCode video below provides an excellent walkthrough of this entire process, including the Python implementation.

To solidify this, let's look at the implementation for the general version of the problem (finding the next greater element for all items in a single array).

The final Python code looks like this:

def nextGreaterElement(nums):
    n = len(nums)
    result = [-1] * n  # Initialize result with -1
    stack = []  # This will store indices

    for i in range(n):



        # While stack is not empty AND current element is greater than
        # the element at the index on top of the stack
        while stack and nums[i] > nums[stack[-1]]:



            # We found the next greater element for the index on top of the stack
            index = stack.pop()
            result[index] = nums[i]
        



        # Push current index onto the stack
        stack.append(i)

    return result




# Example
print(nextGreaterElement([2, 1, 3, 2, 4, 3]))



# Output: [3, 3, 4, 4, -1, -1]

Applying the Pattern: Daily Temperatures

Once you understand the "Next Greater Element" pattern, you can solve a variety of related interview problems. A classic example is "Daily Temperatures" (LeetCode 739).

The problem asks: Given an array of daily temperatures, return an array where each element is the number of days you have to wait until a warmer temperature. If there is no future day for which this is possible, put 0.

This is just a slight variation of "Next Greater Element". Instead of storing the value of the next greater element, we need to store the distance between the indices. The logic remains identical.

The following video provides a fantastic explanation.

Conclusion

In this lesson, you've added a sophisticated and efficient pattern to your algorithmic toolkit. The monotonic stack is a prime example of how choosing the right data structure can transform a slow algorithm into a highly optimized one.

Key Takeaways:

• A monotonic stack is a stack that maintains its elements in a sorted (non-increasing or non-decreasing) order.
• It is the go-to pattern for finding the "next/previous greater/smaller element" in a sequence, achieving this in $O(n)$ time and space.
• The core mechanism involves a while loop that pops elements from the stack whenever a new element from the input array would violate the monotonic property, resolving the search for those popped elements.
• Storing indices on the stack, rather than values, is often the key to solving these problems, as it allows you to calculate distances or update a result array at the correct position.

In our next lesson, we will continue our exploration of specialized stacks by learning how to design and implement a Min Stack. This data structure supports all standard stack operations, plus an additional getMin operation that returns the minimum element in the stack in constant time.