Next Greater Element
For each element, find the first larger element to its right (−1 if none).
Open on GeeksforGeeks ↗02
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'.
03
Approach
1
Waiting room, not lookahead
Instead of scanning right for each element (O(n²)), let elements wait until their answer arrives.
2
Pop while smaller
New value x pops every stack element < x — x is their next greater. Then x itself waits.
3
Amortized O(n)
Each element is pushed and popped at most once, so total work is linear despite the inner while.
04
Solution & live demo
python
▶1def next_greater(nums):
▶2 res = [-1] * len(nums)
▶3 stack = [] # indices, values decreasing
▶4 for i, x in enumerate(nums):
▶5 while stack and nums[stack[-1]] < x:
▶6 res[stack.pop()] = x
▶7 stack.append(i)
▶8 return res
05
Edge cases
Decreasing array
Nothing ever pops; everyone drains at the end with −1.
Duplicates
Pop strictly-smaller only; equal values keep waiting (their next greater must be strictly bigger).
06
Complexity
Time
O(n)
Space
O(n)
Each index pushed/popped once.