Monotonic Stack (Next Greater Element)

The problem

For every element of an array, find the next element to its right that is strictly greater, or −1 if none exists.

For [4, 5, 2, 10, 8, 6, 12] the answer is [5, 10, 10, 12, 12, 12, −1].

The brute-force way compares every pair in O(n²). A stack does it in O(n).

The idea

Keep a stack of indices whose answer is still unknown. When a new value a[i] arrives:

1. While the value on top of the stack is smaller than a[i], then a[i] is its next greater element. Record it and pop.
2. Push i.

Because we pop every smaller value before pushing, the values on the stack are always decreasing from bottom to top. That ordering is what the word monotonic means.

stack ← empty;   result ← all −1
for i from 0 to n − 1:
    while stack is not empty and a[stack.top] < a[i]:
        result[stack.top] ← a[i]
        stack.pop()
    stack.push(i)

Why it is O(n)

Each index is pushed exactly once and popped at most once, so the inner while loop does at most n pops over the whole run. Total work is at most 2n.

Code

def next_greater(a):
    result = [-1] * len(a)
    stack = []                       # indices, values decreasing
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([4, 5, 2, 10, 8, 6, 12]))   # [5, 10, 10, 12, 12, 12, -1]

Where is it used?

The same pattern solves many interview and contest problems:

• Daily temperatures: how many days until a warmer day.
• Stock span: how many consecutive earlier days had a lower price.
• Largest rectangle in a histogram and trapping rain water.
• Flip the comparison to find the next smaller element.

Common mistakes

• Storing values instead of indices. You need the index to write the answer in the right place.
• Using <= when the problem asks for a strictly greater element, which changes how equal values behave.
• Forgetting the elements left on the stack at the end. Their answer stays −1.
• Scanning left to right for a “previous greater” problem. Flip the direction or the comparison to match the question.