Next Greater Element II
For each element in a circular array, find the next greater element, searching wrap-around; return -1 where none exists.
Open on LeetCode ↗Intuition
The trap is writing an answer on every visit to index i, including the first lap. Loop 2n times with i % n, and the first lap (when i >= n) is only there to preload the stack with elements from the front of the array — write to res[i] on that lap and you overwrite a correct answer with a partial one computed before the stack was full. The fix is a single guard: only record res[i] when i < n, the real, final lap.
The circular version of next-greater. Walking 2n - 1 down to 0 with i % n simulates two laps, so every element sees the wrap-around; results are only recorded on the second lap, when the stack already holds everything to the right.
Approach
Recall the linear monotonic stack
Walk right to left keeping a stack of candidates in decreasing order. Before reading the answer for i, pop everything at or below nums[i] — those can never be anyone's next greater element while nums[i] sits in front of them. Whatever remains on top is the answer, or -1 if the stack empties.
Handle the wrap with a double loop
Run i from 2n - 1 down to 0 and use nums[i % n]. By the time the index reaches the original range, the stack already holds the elements from the front of the array, so wrap-around lookups resolve naturally without duplicating the array in memory.
Only write answers on the real lap
During the first lap (i >= n) just maintain the stack — push and pop but record nothing. Once i < n, write res[i]. Drop the i < n guard and the code still runs and still looks plausible, because the loop only ever writes res[i % n] — but on the first lap the stack has not seen the whole array yet, so those early writes are wrong and get silently left in place if the real lap never overwrites the same slot correctly. Each element is pushed and popped at most twice, so the total is O(n) time and O(n) space.
Solution & live demo
Common pitfalls
Recording results on both laps
if st: res[i % n] = st[-1]
if i < n and st:
res[i] = st[-1]During the first (higher-index) lap the stack hasn't yet seen the wrapped elements, so the answers are incomplete. The extra lap exists only to prime the stack; writes must wait until i is a real index.
Popping on strict greater-than
while st and st[-1] < cur:
while st and st[-1] <= cur:
"Next greater" is strict, so an equal value is not an answer and must be discarded. Keeping equals makes the stack report a same-valued element as the next greater one.
Doubling the array instead
nums = nums + nums
cur = nums[i % n]
Functionally the same but allocates a second array. The modulo indexing gets the identical traversal with no extra space, which matters when the array is large.
Edge cases
Strict > means nothing qualifies, so every answer is -1.
The maximum gets -1 and everything else points to its right neighbour.
It cannot exceed itself, so the answer is [-1].
Always -1, since nothing anywhere in the circle is greater.