Next Greater Element
Medium · rating 1450 · Stack, Arrays
The first line contains n. The second line has n integers. For each element print the next element to its right that is strictly greater, or -1 if none exists. Output the n answers space-separated.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
A monotonic stack answers all queries in one pass. Keep a stack of indices whose next-greater element is still unknown. When a new value arrives, it resolves every smaller value waiting on the stack — pop them and record the new value as their answer — then push the new index.
Key insight
Each index is pushed once and popped once, so the total work is linear even though it looks nested.
res = [-1] * n
stack = []
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
res[stack.pop()] = x
stack.append(i)Complexity
Time: O(n). Space: O(n).
Related problems
- Product of Array Except Self — Hard
- Count Pairs With Difference — Medium
- Count Pairs with Sum — Medium
- Maximum Subarray Sum — Medium
- Balanced Brackets — Medium
- Longest Increasing Subsequence — Hard