Next Greater Element

Next Greater Element asks a simple-sounding question for every item in an array: looking only to the right, what is the first value bigger than me? The naive answer is a nested loop, but a monotonic stack answers all of them in a single pass.

The slow way first

The obvious idea: for each element, scan everything to its right until you find something bigger. That works, but it is O(n²) — every element may re-scan most of the array. For a long input it is far too slow.

The question to ask: when I move past an element, can I remember it and resolve it later, exactly once? If I could keep a short list of "still waiting" elements and knock them out the moment a bigger value appears, each element would be pushed and popped a single time — that is O(n).

The idea: a decreasing stack of waiting indices

Keep a stack of indices whose next greater element is still unknown. Walk left to right. For each new value num, look at the top of the stack: while the value there is smaller than num, that element has just found its answer — pop it and record num as its next greater. Then push the current index.

The stack always stays decreasing from bottom to top, because we pop anything smaller before pushing. Whatever is left on the stack at the end never found a greater value, so it keeps its -1.

Walk through it

Step through the animation. The pointer i scans left to right and the stack row underneath holds the waiting indices. When i reaches 3, both waiting indices (2 and 1, holding values 2 and 3) are smaller than 4, so they pop in one burst and both get answer 4. Index 3 ends up alone on the stack, so its result stays -1.

Pseudocode

result = array of -1, same length as nums
stack  = empty list of indices
for each index i with value num in nums:
    while stack is not empty and nums[stack.top] < num:
        j = stack.pop()
        result[j] = num            # num is j's next greater element
    push i onto stack              # i now waits for its own greater value
return result                      # leftovers on the stack stay -1

The Python solution

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # indices waiting for a greater value
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            j = stack.pop()
            result[j] = num
        stack.append(i)
    return result

• result starts all -1, so any index never resolved keeps that default.
• stack holds indices, not values, so we can write the answer back into result[j].
• Line 5 is the heart of the trick: while the value at the stack top is smaller than num, that element has found its next greater.
• We pop in a while loop because one big value can resolve several waiting elements at once.
• stack.append(i) adds the current index, which now waits for its own greater value to appear later.

Complexity

Even though there is a while loop inside the for loop, every index is pushed once and popped at most once, so the total work is O(n). The stack uses O(n) extra space in the worst case (a strictly decreasing array, where nothing pops until the end).

When this pattern shows up

Practice