Monotonic Stack Pattern: Template + 225 LeetCode Problems

What the monotonic stack pattern is

A monotonic stack is an ordinary stack with one invariant added: its contents are kept increasing or decreasing, and any element that would break the order is popped first. The pops are the algorithm. When a new value evicts the elements below it, that new value is by construction the nearest element to their right that is larger — so "next greater element" for every index falls out of a single left-to-right scan rather than an O(n²) search. The total cost stays linear because each index is pushed once and popped once, no matter how expensive an individual step looks. Pick the direction from the question: a decreasing stack surrenders its top to a larger arrival and answers next-greater queries, an increasing stack answers next-smaller, and storing indices rather than values is almost always right because the distance between them is usually part of the answer.

When to use it

• —The question is about the nearest larger or smaller element in some direction.
• —You are computing spans, widths or distances between a position and the first position that beats it.
• —A histogram, a skyline, temperatures, or stock spans are involved.
• —The brute force scans right from every index until it finds something bigger.

The monotonic stack template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 225 problems listed below.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indices; their values stay decreasing

    for i, value in enumerate(nums):
        # every index this value evicts has just found its next greater element
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = value
        stack.append(i)

    return result

Complexity characteristics

Time

O(n)

Auxiliary space

O(n)

Each index is pushed exactly once and popped at most once, so the inner while loop does not multiply the outer loop: the total number of pops over the whole scan is bounded by n even though one step can pop many elements. The stack is the space, and it holds all n indices in the worst case — an input already sorted in the direction the stack maintains never pops anything until the end.

All 225 monotonic stack LeetCode problems

Every problem in the library the monotonic stack pattern applies to, grouped by LeetCode's own difficulty rating. 184 of the 225 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Monotonic Stack pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.