071. Next Greater Element

Why this mechanism works

Instead of searching the future separately for every cell, let each incoming value resolve earlier pending cells. A stack holds their indices in nonincreasing value order. If the incoming value is greater than the top, it is the first qualifying value for that unresolved position.

State and boundaries

stack contains indices still waiting for a strictly greater value; their values are nonincreasing from bottom to top.

Protocol

1. Initialize answers to -1.
2. For each incoming value pop every strictly smaller pending top.
3. Set each popped answer to the incoming value.
4. Push the current index.

Visualization

pending indices for values [2,1,2]
incoming 4 resolves both 2s
next greater is about position, not minimum magnitude

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 next_greater: answer = [-1] * len(nums)
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]

L3 next_greater: stack = []
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[]

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[]; i=0; value=2

L7 next_greater: stack.append(i)
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[0]; i=0; value=2

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[0]; i=1; value=1

L7 next_greater: stack.append(i)
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[0, 1]; i=1; value=1

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 1, 2, 4, 3]; answer=[-1, -1, -1, -1, -1]; stack=[0, 1]; i=2; value=2

L6 next_greater: answer[stack.pop()] = value
nums=[2, 1, 2, 4, 3]; answer=[-1, 2, -1, -1, -1]; stack=[0]; i=2; value=2

... 3 intermediate state changes omitted ...

L6 next_greater: answer[stack.pop()] = value
nums=[2, 1, 2, 4, 3]; answer=[4, 2, 4, -1, -1]; stack=[]; i=3; value=4

L7 next_greater: stack.append(i)
nums=[2, 1, 2, 4, 3]; answer=[4, 2, 4, -1, -1]; stack=[3]; i=3; value=4

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 1, 2, 4, 3]; answer=[4, 2, 4, -1, -1]; stack=[3]; i=4; value=3

L7 next_greater: stack.append(i)
nums=[2, 1, 2, 4, 3]; answer=[4, 2, 4, -1, -1]; stack=[3, 4]; i=4; value=3

L2 next_greater: answer = [-1] * len(nums)
nums=[2, 2]; answer=[-1, -1]

L3 next_greater: stack = []
nums=[2, 2]; answer=[-1, -1]; stack=[]

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 2]; answer=[-1, -1]; stack=[]; i=0; value=2

L7 next_greater: stack.append(i)
nums=[2, 2]; answer=[-1, -1]; stack=[0]; i=0; value=2

L4 next_greater: for i, value in enumerate(nums):
nums=[2, 2]; answer=[-1, -1]; stack=[0]; i=1; value=2

L7 next_greater: stack.append(i)
nums=[2, 2]; answer=[-1, -1]; stack=[0, 1]; i=1; value=2

Why the solution is correct

Any earlier greater value would already have removed a pending index. Therefore the value that finally pops it is its first greater successor. Indices left on the stack have no qualifying successor and retain -1.

Time and space

O(n) time and O(n) space; every index is pushed and popped at most once.

Common mistakes

Using >= when resolving makes equal values qualify incorrectly. Storing only values cannot assign results to repeated positions reliably.

Reasoning card

Transfer exercise

Return distances instead of values, or treat the array as circular while ensuring each index receives only its first answer.