263. Next Greater Element II

Simulate the circular array by iterating 2·n times with index i%n. A decreasing stack of indices resolves each element's next-greater; only push indices in the first pass.

Handle the wrap-around

A circular array means an element's next-greater may lie past the end. Iterate i from 0 to 2n-1 using nums[i % n]. Keep a stack of indices with strictly decreasing values; when the current value exceeds nums[stack.top], it's that index's answer.

Only push indices during the first n iterations (the second pass just resolves wrap-arounds).

res = [-1]*n
for i in range(2n):
    cur = nums[i%n]
    while stack and nums[stack[-1]] < cur: res[stack.pop()] = cur
    if i < n: stack.append(i)
return res

Worked example

[1,2,1] → [2,-1,2] (the last 1 wraps to the leading 2).

Complexity

• Time: O(n).
• Space: O(n).

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();  // indices
        for (int i = 0; i < 2 * n; i++) {
            int cur = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < cur) {
                res[stack.pop()] = cur;
            }
            if (i < n) stack.push(i);
        }
        return res;
    }
}