All problems

Next Greater Element II

Medium · stack

You are given a list nums that is arranged in a circle: after the last number comes the first one again, and the walk can keep going round.

For each position i, start at the number just after nums[i] and walk round the circle, stopping before you get back to position i. Find the first number you meet that is strictly larger than nums[i].

Return a list of the same length where entry i is that number (the value, not its position), or -1 if no number in the circle is larger than nums[i]. Values can repeat.

Examples

Example 1

Input: nums = [2, 9, 4, 1, 6]

Output: [9, -1, 6, 6, 9]

After 4 comes 1, then 6, so 4 gets 6. After 6 the circle wraps to 2 and then 9, so 6 gets 9. The largest value, 9, has nothing bigger.

Example 2

Input: nums = [3, 3, 3]

Output: [-1, -1, -1]

Equal values do not count as larger.

Example 3

Input: nums = [5, 1, 4]

Output: [-1, 4, 5]

Going round from 4 you reach 5 after wrapping.

Constraints