Next Greater Element
For each element, find the first larger element to its right (−1 if none).
Open on GeeksforGeeks ↗Intuition
Walk the array keeping a stack of elements still waiting for something bigger. Each new element answers — pops — every waiting element smaller than it. The stack is always decreasing top-to-bottom, hence 'monotonic stack'.
"For each element, find the next one that is bigger" is the canonical monotonic-stack question. Keep indices whose answers are still unknown; when a new value arrives, it resolves every pending index it beats. Each index is pushed once and popped once, so the whole thing is O(n) despite the inner loop.
Approach
Waiting room, not lookahead
Instead of scanning right for each element (O(n²)), let elements wait until their answer arrives.
Pop while smaller
New value x pops every stack element < x — x is their next greater. Then x itself waits.
Amortized O(n)
Each element is pushed and popped at most once, so total work is linear despite the inner while.
Solution & live demo
Common pitfalls
Nested loops scanning forward from each index
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
res[i] = nums[j]
breakfor i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
res[stack.pop()] = x
stack.append(i)The rescan is O(n²) and repeats work: if nums[j] failed to answer index i, it also fails for every pending index smaller than it. The stack remembers exactly the unanswered indices, in the order they'll be resolved.
Storing values rather than indices
while stack and stack[-1] < x:
stack.pop()while stack and nums[stack[-1]] < x:
res[stack.pop()] = xThe whole point is to write an answer into res at the position that was waiting for it. With bare values you no longer know which slot the resolved element belongs to.
Not leaving -1 for elements with no greater successor
res = []
res = [-1] * len(nums)
Indices still on the stack at the end never found a bigger value — for them the answer is -1. Pre-filling means those slots are already correct and no post-loop cleanup is needed.
Edge cases
Nothing ever pops; everyone drains at the end with −1.
Pop strictly-smaller only; equal values keep waiting (their next greater must be strictly bigger).