LeetCode 503 Next Greater Element II - Example and Complexity Analysis

Trace [1, 2, 1] with indices 0 to 5 (2n - 1).

i=0: push 0. Stack: [0].

i=1: 2 > 1, pop 0, ans[0] = 2. Push 1. Stack: [1].

i=2: 1 < 2, push 2. Stack: [1, 2].

i=3 (wrap to 0): 1 < 1, no pop. Don't push (i >= n).

i=4 (wrap to 1): 2 > 1, pop 2, ans[2] = 2. 2 == 2, stop popping. Don't push.

i=5 (wrap to 2): 1 < 2, no pop. Don't push.

Result: [2, -1, 2].

Iterate 2n times. Each index pushed once, popped at most once. $O(n)$ time. $O(n)$ space.