Next greater element II

Find the next greater element for every index in a circular array.

arrays stack monotonic stack

Given a list of integers `nums`, return a list of the same length where for each index `i`, the value is the **next greater element** of `nums[i]` in a circular array. The next greater element is the first greater element encountered when moving to the right (increasing indexes), and if you reach the end, wrap around to the beginning. If no such element exists, output `-1`.

Implement the function `next_greater_elements(nums)` that takes a list of integers and returns a list of integers.

**Examples:**
- `next_greater_elements([1,2,1])` → `[2, -1, 2]`
- `next_greater_elements([1,2,3,4,3])` → `[2, 3, 4, -1, 4]`

**Note:** The input list may contain duplicates. The array can be empty.

Constraints

`0 <= len(nums) <= 10^5`
`-10^9 <= nums[i] <= 10^9`

Your solution should run in O(n) time and O(n) space.

Example

>>> next_greater_elements([1,2,1])
[2, -1, 2]
>>> next_greater_elements([1,2,3,4,3])
[2, 3, 4, -1, 4]
>>> next_greater_elements([])
[]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

To handle the circular nature, imagine duplicating the array: for each index i, consider the next n elements from i+1 to i+n.

Use a monotonic decreasing stack of indices. When you find a larger element, it becomes the NGE for the indices in the stack.

You can simulate the circular array by iterating over the doubled array or using modulo arithmetic.

After the first pass, the stack may still have elements. The second pass over the array will resolve most of them; leftover -1 means no greater element.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.