Next Greater Element II

Next greater element ii finds, for each element, the next larger value to its right — but the array is circular, so the search wraps past the end back to the beginning. The non-circular version is a classic monotonic decreasing stack: walk the array holding indices whose next greater element is still unknown, and when a larger value arrives, it resolves every smaller index waiting on the stack. The circularity needs one adjustment, and there is a clean way to get it: - Iterate 2n times using i % n to index, which simulates walking the array twice without allocating a doubled copy. One full pass leaves some indices unresolved; the second pass lets values from the array's start resolve them. Anything still on the stack after both passes genuinely has no greater element anywhere, and stays −1. Actually concatenating the array to itself also works and is easier to picture, but doubles the memory for no benefit. One detail matters in the second pass: do not push indices during it. Every index was already pushed in the first pass, and pushing again creates duplicates that overwrite correct answers. The second pass only pops. The result array must be initialised to −1 so unresolved indices carry the right default without a final cleanup pass. The stack holds indices rather than values, since the answer must be written back to the correct position. Each index is pushed and popped at most once across both passes, so the cost stays O(n) despite the doubled loop.

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.