Next Greater Element II

The key idea

Treat the array as circular by walking the indices twice (i from 0 to 2n-1, using nums[i % n]). Keep a stack of indices whose answer is still unknown, ordered so their values strictly decrease from bottom to top. When the current value exceeds the value at the top index, that top index has just found its next greater element, so pop and record it.

Problem

Given a circular integer array nums (the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Constraints

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

Examples

Input: nums = [1,2,1] Output: [2,-1,2]

Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →