Monotonic Stack Pattern: The Trick Behind Next Greater Element Problems

Monotonic stack problems look intimidating until you notice the repeating structure. You scan through an array while keeping a stack that is always sorted in one direction. That single idea lets you answer "next greater," "next smaller," and several area or span problems in O(n) time.

If you have ever written two nested loops to search for the next bigger value to the right, this pattern is the upgrade.

What Makes a Stack Monotonic?

A stack is monotonic when its elements stay in sorted order:

• decreasing stack for finding next greater elements
• increasing stack for finding next smaller elements

The stack usually stores indices, not values, because you often need positions to compute widths or fill answers.

Classic Example: Next Greater Element

For each number, find the next number to its right that is larger.

def next_greater(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            prev_index = stack.pop()
            result[prev_index] = num
        stack.append(i)

    return result

The stack holds indices whose answer has not been found yet. When a larger value appears, it resolves one or more pending indices.

Why It Stays O(n)

At first glance, the nested while loop looks suspicious. But each index is:

• pushed once
• popped once

That means the total number of stack operations is linear.

Largest Rectangle in Histogram

This is the problem that makes monotonic stacks feel powerful.

def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []
    best = 0

    for i in range(len(heights) + 1):
        current = heights[i] if i < len(heights) else 0

        while stack and heights[stack[-1]] > current:
            h = heights[stack.pop()]
            left_boundary = stack[-1] if stack else -1
            width = i - left_boundary - 1
            best = max(best, h * width)

        stack.append(i)

    return best

The extra zero at the end forces remaining bars to be processed.

Problems It Commonly Solves

• Next Greater Element
• Daily Temperatures
• Stock Span
• Largest Rectangle in Histogram
• Trapping Rain Water (one of several valid approaches)

Recognition Signals

Look for prompts like:

• next greater or next smaller element
• nearest larger value to the left or right
• how many days until a warmer temperature
• widest span constrained by greater/smaller boundaries

These are classic monotonic stack clues.

Common Mistakes

• Storing values when you really need indices
• Using the wrong monotonic direction
• Forgetting to process remaining stack entries at the end
• Not deciding whether equal values should stay or be popped

That last point matters. The choice between < and <= changes how duplicates are handled.

Mental Model

Think of the stack as a list of candidates that are still "waiting" for a future element to prove something:

• a greater value to the right
• a smaller value to the right
• a boundary that closes a rectangle

As soon as a new value invalidates the top candidate, you pop and resolve it.

Complexity

Practice These Next

• Next Greater Element I
• Daily Temperatures
• Online Stock Span
• Largest Rectangle in Histogram
• Maximal Rectangle

Monotonic stacks are a great example of a pattern that looks specialized at first and then starts appearing everywhere once you recognize the shape.