Monotonic Stack

A monotonic stack keeps values or indexes in increasing or decreasing order as the algorithm scans a sequence.

It is useful for nearest-greater, nearest-smaller, and span-like problems.

Core Idea

When a new value arrives, the stack removes values that can no longer be useful. The remaining stack preserves a useful order.

Each element is pushed once and popped at most once, so many monotonic stack algorithms are linear.

Function Contract

next_greater(values) expects a list of comparable values.

It returns a list where each position stores the next value to the right that is greater than values[i]. If no such value exists, the answer for that position is -1.

Python Example

def next_greater(values):
    answer = [-1] * len(values)
    stack = []
 
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            index = stack.pop()
            answer[index] = value
        stack.append(i)
 
    return answer

The stack stores indexes whose next greater value has not been found yet.

Step-by-Step Example

For values = [2, 1, 4], the stack first holds index 0 for value 2, then index 1 for value 1. When 4 appears, it is the next greater value for both 1 and 2, so both indexes are popped and answered.

The stack keeps unresolved candidates. A larger new value resolves all smaller candidates at the top.

Why It Works

If a new value is greater than the value at the top index, that new value is the nearest greater value for that index because everything between them has already been processed and failed to resolve it.

Indexes that remain on the stack are still waiting for a future value strong enough to resolve them.

Complexity

Each index is pushed once and popped at most once. Even though there is a while loop inside the for loop, the total number of pops is at most n, so the algorithm is O(n).

How To Recognize It

A monotonic stack is worth considering when a problem asks for the nearest element to the left or right that is greater, smaller, warmer, colder, taller, or otherwise stronger by some comparison.

The key signal is that a new element can make older elements permanently irrelevant. If an older candidate can still matter after a stronger newer candidate appears, the monotonic-stack idea may not apply.

Common Confusions

The stack usually stores indexes, not just values, because the algorithm often needs to write answers back to the original positions.

“Monotonic” describes the stack’s maintained order. It does not mean the input sequence itself is sorted.

Another common mistake is assuming a nested while means O(n^2). For monotonic stacks, amortized counting is the key.

When To Use It

Use a monotonic stack for next greater element, previous smaller element, histogram rectangles, stock span, and problems where a nearer stronger value makes weaker candidates obsolete.

Do not use it when old candidates do not become permanently useless after a stronger new candidate appears.

The Main Point

A monotonic stack keeps unresolved candidates and removes candidates that a new value makes permanently useless.