Next Greater Element
For every element of an integer array, find the first element to its right that is strictly larger; report -1 when none exists. Values in the array are distinct.
- 1 ≤ n ≤ 10^4
- 0 ≤ nums[i] ≤ 10^4
- All values distinct
- "First larger element to the right"
- Candidates still waiting form a decreasing stack
- Amortized linear: each element is pushed and popped once
Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.
Iterate over the array maintaining a stack of values with no answer yet; they are in decreasing order. When a new value arrives, pop every smaller stack element and set its answer to the new value, then push the new value. Elements never popped get -1. Because a popped element is resolved immediately and never revisited, total work is linear.
- Nested loops cost O(n^2). For circular variants, iterate over the array twice while keeping the same stack.