Monotonic Stacks from Scratch: Starting with the Next Greater Element

Table of contents

First, what is a stack?

A stack is a container you can only add to and remove from at one end. The best analogy is a stack of plates:

• A clean plate can only go on top.
• When you need a plate, you can only take the one on top.

So the last plate in is the first one out, known as “last in, first out”. The top position is called the top of the stack, and the other end is the bottom.

In Python, a plain list works as a stack with just three operations:

stack: list[int] = []

stack.append(3)  # Put one on top: [3]
stack.append(1)  # Put another: [3, 1], the top is 1
top = stack[-1]  # Peek at the top without removing it: 1
stack.pop()  # Remove the top: [3]

In this post, a stack is always written left to right, with the bottom on the left and the top on the right. For example, [3, 1] means 3 is underneath and 1 is on top.

What makes a stack “monotonic”

A monotonic stack is a stack whose elements always stay in order from bottom to top, either always decreasing or always increasing.

• Always getting smaller from bottom to top is a monotonically decreasing stack, like [9, 6, 4, 1].
• Always getting larger is a monotonically increasing stack, like [1, 4, 6, 9].

The definition alone doesn’t explain why anyone would want this. A monotonic stack isn’t something you design up front; it shows up naturally when you solve a certain kind of problem. So let’s start with that problem.

The problem: the next greater element

Given an array of integers, find, for each element, the first element to its right that is greater than it. If there isn’t one, use -1.

Example: nums = [3, 1, 2, 5, 4]

The answer is [5, 2, 5, -1, -1].

Brute force

Do exactly what the table does: for each element, scan right one by one.

def next_greater_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for later in nums[i + 1 :]:
            if later > num:
                answer[i] = later
                break
    return answer

In the worst case (say, an array that only decreases, so nobody finds an answer), every element scans to the end, which is O(n²).

It’s slow because the same elements get scanned over and over. Index 0 already looked at 1, 2, and 5, and then index 1 looks at them again.

Flip it around: let elements arrive and see who gets answered

Brute force has each element go looking for its answer. Flip the perspective: let the elements arrive one at a time from the left, and each time one arrives, ask whose answer it is.

Think of each number as a person, with the value as their height. Everyone wants to know: “Who is the first person to my right who is taller than me?”

• People walk into a room one at a time, from left to right.
• The room has a waiting area where everyone who hasn’t found their answer stands.
• When a new person walks in, everyone in the waiting area shorter than them has found their answer, the new person, and leaves.
• Then the new person joins the waiting area to wait for someone taller.
• After everyone has arrived, anyone still waiting has nobody taller to their right, so their answer is -1.

Step by step

Same nums = [3, 1, 2, 5, 4]. The waiting area is listed left to right in order of arrival.

Step 1: 3 arrives

• The waiting area is empty, so nobody gets an answer.
• 3 joins the waiting area.
• Waiting: [3]

Step 2: 1 arrives

• The most recent arrival is 3. 1 is shorter than 3, so 3 gets no answer.
• 1 joins the waiting area.
• Waiting: [3, 1]

Step 3: 2 arrives

• Check the most recent arrival, 1: 2 is taller, so 1’s answer is 2, and 1 leaves.
• Check 3: 2 is shorter, so 3 gets no answer. Stop.
• 2 joins the waiting area.
• Waiting: [3, 2]

Step 4: 5 arrives

• Check the most recent arrival, 2: 5 is taller, so 2’s answer is 5, and 2 leaves.
• Check 3: 5 is taller, so 3’s answer is 5, and 3 leaves.
• The waiting area is empty. Stop.
• 5 joins the waiting area.
• Waiting: [5]

Step 5: 4 arrives

• Check 5: 4 is shorter, so 5 gets no answer. Stop.
• 4 joins the waiting area.
• Waiting: [5, 4]

After everyone has arrived: 5 and 4 are still waiting, so both answers are -1.

As a table:

Answers: 3→5, 1→2, 2→5, 5→-1, 4→-1, or [5, 2, 5, -1, -1], the same as brute force.

The key insight: the waiting area always decreases from left to right

Look at the last column: [3], [3, 1], [3, 2], [5], [5, 4]. Every one of them gets shorter from left to right. That’s not a coincidence; it has to be this way:

Suppose a shorter person A stood to the left of a taller person B in the waiting area (A arrived first, B later, and A is shorter than B). Then the moment B arrived, A would have gotten an answer and left. So this situation can’t exist.

Since the waiting area always decreases, two useful facts follow:

1. When someone new arrives, check from the most recent arrival backward. As soon as you meet someone who isn’t shorter than the newcomer, stop: everyone further back is even taller and can’t be answered either.
2. People always leave and join at the same end (the right). That’s exactly last in, first out: a stack.

This always-decreasing waiting area is a monotonically decreasing stack. Nobody forced it to decrease; it happens naturally from the rule that people without an answer stay behind.

In code

In real code, the stack usually holds indices rather than values. When an element gets its answer, we need to know which position to fill. An index lets us recover the value (nums[i]) and fill the right slot.

def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    waiting: list[int] = []  # Indices still waiting; values decrease bottom to top

    for i, num in enumerate(nums):
        # The new element is greater than the top: the top has its answer
        while waiting and num > nums[waiting[-1]]:
            answer[waiting.pop()] = num
        waiting.append(i)

    return answer

The stack is named waiting on purpose, to say what it holds: elements still waiting for an answer. Anything left on the stack at the end needs no handling, because answer starts out filled with -1.

Matching the code to the steps above:

• The while loop is “check from the most recent arrival backward; anyone shorter gets an answer and leaves”.
• waiting.append(i) is “the newcomer joins the waiting area”.

Why it’s O(n)

Two nested loops look like O(n²), but they aren’t. Count it differently: each index is pushed at most once and popped at most once. Every pass through the while loop pops one element, so across the whole run there are at most n pops. The total time is O(n), and the space is O(n) too (in the worst case, such as a decreasing array, everything is on the stack).

A twist: return the distance instead of the value

Many problems don’t ask what the next greater element is, but how many steps to the right it is. For example: given daily temperatures, how many days does each day have to wait for a warmer one?

This is where storing indices pays off: when an element gets its answer, subtract its index from the current index to get the distance.

def days_until_warmer(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    waiting: list[int] = []  # Days that haven't seen a warmer day yet

    for today, temperature in enumerate(temperatures):
        while waiting and temperature > temperatures[waiting[-1]]:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)

    return answer

days_until_warmer([3, 1, 2, 5, 4]) returns [3, 1, 1, 0, 0]: day 0 waits 3 days (until the 5 on day 3), day 1 waits 1 day, and so on; days that never get warmer are 0.

That’s exactly 739. Daily Temperatures from the Top 100 Liked list.

A bonus: the top at push time is the nearest element to the left that isn’t smaller

A monotonic stack has another property that’s easy to miss. When a new element has finished popping everything smaller and is about to be pushed, the current top is the first element to its left that is greater than or equal to it.

From the steps above:

• When 2 arrives and pops 1, the top is 3, so the first element left of 2 that isn’t smaller is 3.
• When 4 arrives, nothing is popped and the top is 5, so the first element left of 4 that isn’t smaller is 5.

The reason is the same as before: everything smaller has been popped, so whatever remains on top is the closest element that isn’t smaller.

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

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            stack.pop()
        if stack:
            answer[i] = nums[stack[-1]]
        stack.append(i)

    return answer

previous_greater_or_equal([3, 1, 2, 5, 4]) returns [-1, 3, 3, -1, 5].

In other words, one scan gives you two things at once: when an element is popped, the element that popped it is the first greater one to its right, and the new top after the pop is the first one to its left that isn’t smaller. The monotonic stack solution to Trapping Rain Water relies on exactly this: those two taller neighbors are the left and right walls of a dip.

The template and its variants

Abstracting the code above, a monotonic stack is just a few lines (this is pseudocode; replace should_pop and the handling steps for each problem):

stack = []
for i, num in enumerate(nums):
    while stack is not empty and should_pop(nums[stack[-1]], num):
        top = stack.pop()
        handle top: num is the first element to the right of top that meets the condition
    handle i: if stack is not empty, stack[-1] is the first element to the left of i that doesn't meet the pop condition
    stack.append(i)

Change the pop condition to find different things:

A way to remember it: to find something greater, let the smaller elements get popped, and what remains is naturally decreasing. To find something smaller, do the opposite.

When to reach for a monotonic stack

Consider one when a problem says things like:

• “the next greater / smaller element”;
• “the first element to the left / right that is greater / smaller”;
• “how many days / steps until…”;
• finding ranges “enclosed” by taller (or shorter) elements on both sides, as in Trapping Rain Water or the largest rectangle in a histogram.

Monotonic stack problems in the Top 100 Liked list:

Common pitfalls

1. Storing values or indices: most problems need indices. An index can recover the value and also gives you distances and the slot to fill; with values alone, that information is lost.
2. Strict or non-strict comparison: > versus >= decides whether equal elements pop each other, which can change the result. Decide up front whether “equal” counts as “greater”.
3. Forgetting what’s left on the stack: those elements never found an answer. This post initializes the answers to -1 or 0, so nothing extra is needed. If a problem treats them specially, handle them after the loop.
4. Worrying that it’s O(n²): don’t let the nested loops fool you. Count “each element is pushed and popped at most once”, and it’s O(n).

In one sentence

A monotonic stack is a waiting area for elements still looking for their answer. When a new element arrives, it settles everything smaller (or larger) than itself, and what remains stays in order. That lets you find, for every element, the first greater (or smaller) element to its left or right in O(n) time.

Appendix: full test code

The three functions from this post and their brute-force counterparts, cross-checked on 3,000 random inputs:

"""Cross-check the monotonic stack functions against brute force."""

import random
from collections.abc import Callable


def next_greater_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for later in nums[i + 1 :]:
            if later > num:
                answer[i] = later
                break
    return answer


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

    for i, num in enumerate(nums):
        while waiting and num > nums[waiting[-1]]:
            answer[waiting.pop()] = num
        waiting.append(i)

    return answer


def days_until_warmer(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    waiting: list[int] = []

    for today, temperature in enumerate(temperatures):
        while waiting and temperature > temperatures[waiting[-1]]:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)

    return answer


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

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            stack.pop()
        if stack:
            answer[i] = nums[stack[-1]]
        stack.append(i)

    return answer


def days_until_warmer_brute_force(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    for day, temperature in enumerate(temperatures):
        for later in range(day + 1, len(temperatures)):
            if temperatures[later] > temperature:
                answer[day] = later - day
                break
    return answer


def previous_greater_or_equal_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for earlier in reversed(nums[:i]):
            if earlier >= num:
                answer[i] = earlier
                break
    return answer


Scan = Callable[[list[int]], list[int]]

# (monotonic stack version, brute-force version)
PAIRS: list[tuple[Scan, Scan]] = [
    (next_greater, next_greater_brute_force),
    (days_until_warmer, days_until_warmer_brute_force),
    (previous_greater_or_equal, previous_greater_or_equal_brute_force),
]


def check_fixed_cases() -> None:
    assert next_greater([3, 1, 2, 5, 4]) == [5, 2, 5, -1, -1]
    assert next_greater([]) == []
    assert days_until_warmer([3, 1, 2, 5, 4]) == [3, 1, 1, 0, 0]
    assert previous_greater_or_equal([3, 1, 2, 5, 4]) == [-1, 3, 3, -1, 5]


def check_random_cases(rounds: int = 3000, seed: int = 0) -> None:
    rng = random.Random(seed)
    for _ in range(rounds):
        nums = [rng.randint(0, 6) for _ in range(rng.randint(0, 20))]
        for fast, slow in PAIRS:
            assert fast(nums) == slow(nums), f"{fast.__name__}({nums})"


def main() -> None:
    check_fixed_cases()
    check_random_cases()
    print("all passed")


if __name__ == "__main__":
    main()