Monotonic Stack: Find the Next Greater Element

By Hourly DSA · September 20, 2026 · 4 min read

A monotonic stack keeps pending elements in a consistent value order, letting a new element resolve earlier questions without scanning backward repeatedly. For the next greater element problem, scan left to right and keep indices whose answers are still unknown.

When a larger value arrives, it becomes the answer for smaller values at the top of the stack. Each resolved index leaves the stack permanently.

First, define what “next greater” means

For every position, find the first value strictly greater than it somewhere to its right. “Next” refers to the nearest qualifying position, not the greatest value in the remaining array.

For example:

values:  [3, 1, 4, 2, 5]
answers: [4, 4, 5, 5, none]

The answer for 3 is 4, even though 5 is larger. The answer for the final 5 is absent because nothing follows it.

A direct solution starts a fresh rightward scan at every position. On a decreasing array, each scan reaches the end, producing O(n²) work. The stack avoids revisiting elements whose answer has already been found.

Keep unresolved indices on the stack

Process [3, 1, 4, 2, 5] from left to right:

Read 3. There are no pending elements. Push its index.
Read 1. It is not greater than 3. Push its index above 3's.
Read 4. It is greater than 1, so resolve 1's answer as 4 and pop. It is also greater than 3, so resolve 3's answer as 4 and pop. Push 4's index.
Read 2. It cannot resolve 4. Push its index.
Read 5. Resolve 2 and then 4. Push 5's index.

The remaining index belongs to 5. Its answer stays absent.

Store indices rather than only values so you can write each answer in the correct output position. Indices also let you return a distance, such as the number of days until a warmer temperature, when that is what the problem requests.

Why the stack order is useful

From bottom to top, pending values are nonincreasing. A smaller incoming value can wait above a larger one. A larger incoming value pops smaller values until that order is restored.

When 4 resolves 1 and 3 in the example, it is their first greater value to the right. If an earlier qualifying value had appeared, those indices would already have been removed.

Once the top is at least as large as the incoming value, everything below the top is also at least as large. The current value cannot resolve any of them, so checking deeper would be wasted work.

This is the invariant: a property that remains true after every iteration. The USACO Guide's monotonic stack lesson illustrates the related nearest-smaller-element pattern.

The pseudocode fits in a short scan

Initialize every answer to none, then run:

pending = empty stack
for i from 0 through n - 1:
    while pending is not empty and values[pending.top] < values[i]:
        previous = pending.pop()
        answer[previous] = values[i]
    pending.push(i)

The strict comparison is deliberate. With [2, 2, 3], both 2s should receive 3 as their next strictly greater value. The second 2 must not resolve the first.

If the question asks for the next greater or equal value, the pop condition changes to <=. That is a change in the problem's meaning, not a cosmetic implementation choice.

Why the nested loop is still O(n)

Each index is pushed once. It can be popped at most once. Across the entire scan, there are at most n pushes and n pops.

A single incoming value might pop many indices, but those indices never return. The total work is O(n), with O(n) auxiliary stack space in the worst case. The output array also contains n entries.

This is an example of counting total work across iterations. If nested loops make you immediately guess O(n²), revisit Big O through small examples.

Recognize when the pattern fits

Look for a question about a nearest greater or smaller element, unresolved earlier positions, or a new value that makes older candidates unnecessary.

Then specify the direction and comparison. Next greater to the right, previous smaller to the left, and greater-or-equal variants have different stack rules. A memorized pop condition can quietly answer the wrong question.

For [5, 3, 4], what is the next greater value for 3? 4. What is it for 5? None. The fact that 5 is larger than every other value does not give it an answer to its right.

If the basic push and pop behavior is still unfamiliar, start with stack vs. queue. Use Hourly DSA to keep practicing small traces and the reasoning behind each removal.