Problem

Given a circular integer array nums (i.e., 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.

Examples

Example 1:

1
2
3
4
5

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

1
2

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

Solution

Method 1 - Monotonic Decreasing Stack on Indices with Twice the Loop

This is similar to NGR - Nearest Greater Element to Right of every element OR Next Greater Element 1. But we need to use indices as input to the stack and also we have to loop twice:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int[] nextGreaterElements(int[] nums) {
	int n = nums.length, ans[] = new int[n];

	Arrays.fill(ans, -1);

	Stack<Integer> stack = new Stack<>();
	
	for (int i = 0; i <n * 2; i++) {
		while (!stack.isEmpty() && nums[stack.peek()]<nums[i % n]) {
			ans[stack.pop()] = nums[i % n];
		}
		stack.push(i % n);
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)