Why it works
- Going around the circle from any index, the next greater number is at most n − 1 steps away. Two laps cover that for every index, the last ones included.
- The first lap pushes every index once. The second lap only answers the indices still waiting: it pushes nothing, so no index is answered twice and none waits for itself.
- Whatever is left on the stack after two laps is the largest number, maybe repeated: nothing in the whole circle beats it, so -1 is right.
Complexity
Time O(n): 2n steps of the loop, and each index is pushed once and popped at most once. Memory O(n) for the stack and the answer.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗