Monotonic Stacks

To see how high you can build, you must first find the nearest wall that is taller than you.

Imagine you're looking at a series of buildings and, for each one, you want to find the first building to its right that is taller. A naive approach would be to scan forward from every single building, but that's slow. How can we do better?

This is the kind of "next greater element" problem where a Monotonic Stack provides an elegant and efficient $O(n)$ solution.

Problem: Next Greater Element I (LeetCode Link): You are given two arrays nums1 and nums2 where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, the answer for this query is -1. 💡 Hint

The Brute-Force Approach

The most straightforward way is to iterate through nums2. For each element, you'd then have a nested loop that scans the rest of the array to its right to find the first element that is greater. This works, but it's $O(n^2)$ —too slow for large inputs.

The Monotonic Stack Solution

A Monotonic Stack is a stack that keeps its elements in a specific order (either always increasing or always decreasing). It's the perfect tool for "next/previous greater/smaller element" problems.

The core idea is to process the array once, using the stack to keep track of elements that are still "looking for" their next greater element.

Monotonic Decreasing Stack: If we want to find the next greater element, we use a decreasing stack. As we iterate through the array, we ensure the stack always remains in decreasing order.
Monotonic Increasing Stack: If we want to find the next smaller element, we use an increasing stack.

How it Works (for Next Greater Element)

We iterate through the array, and for each element num:

Look at the top of the stack. While the stack is not empty and the element at the top is smaller than our current num, we have found the "next greater element" for the element at the top. We pop it and record the answer.
We keep popping until the stack is empty or its top is greater than or equal to num.
Finally, we push the current num (or its index) onto the stack. It will now wait for its next greater element.

This ensures that the stack always holds a sequence of elements in decreasing order.

General Template

Here is a template for finding the next greater element.

def next_greater_element_template(nums):
    stack = []  # Will store indices
    result = [-1] * len(nums)

    for i, num in enumerate(nums):
        # While stack is not empty and the current element is greater
        # than the element at the index on top of the stack
        while stack and nums[stack[-1]] < num:
            prev_index = stack.pop()
            result[prev_index] = num
        stack.append(i)
    
    return result

public int[] nextGreaterElementTemplate(int[] nums) {
    Stack<Integer> stack = new Stack<>(); // Stores indices
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);

    for (int i = 0; i < nums.length; i++) {
        // While stack is not empty and current element is greater
        // than the element at the index on top of the stack
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int prevIndex = stack.pop();
            result[prevIndex] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Walkthrough: Solving "Daily Temperatures"

This is a slight variation where we need the distance to the next greater element.

Problem: Daily Temperatures (LeetCode Link): Given a list of daily temperatures, produce a list that, for each day, tells you how many days you would have to wait until a warmer temperature.

We use the same monotonic decreasing stack logic, but instead of storing the value, we store the number of days.

def daily_temperatures(temperatures):
    stack = []  # Stores indices
    result = [0] * len(temperatures)

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index  # The distance is the difference in indices
        stack.append(i)

    return result

public int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>(); // Stores indices
    int[] result = new int[temperatures.length];

    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex; // The distance
        }
        stack.push(i);
    }
    return result;
}

Bonus Point: Largest Rectangle in Histogram

A much harder, classic problem that uses this pattern is Largest Rectangle in Histogram (LeetCode Link).

The insight here is that for any bar, the largest rectangle that includes that bar extends to the left and right until it hits a bar that is shorter. You can use a monotonic (increasing) stack to find the previous smaller element and the next smaller element for every bar. The distance between these two boundaries gives you the width of the largest possible rectangle for that bar. By calculating this for every bar, you can find the overall maximum area. This is a brilliant and non-obvious application of the monotonic stack pattern.