Next Greater Element II

Problem Statement

The task involves processing a circular integer array named nums. In a circular array, envision the array as something that connects end-to-end. Thus, the element following the array's last element is its first element. For each element in the array nums, we need to determine its next greater number. Conceptually, the next greater number of an element x in nums is defined as the nearest subsequent number in the array that is greater than x. This search wraps around to the start of the array when necessary. If no larger number exists, the result for that element should be -1.

Examples

Example 1

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

Input:

nums = [1,2,3,4,3]

Output:

[2,3,4,-1,4]

Constraints

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

Approach and Intuition

To efficiently solve the problem, we can utilize a combination of a stack and the circular array properties. Here's a high-level breakdown:

1. Stack for Greater Elements: Use a stack to keep track of the indices of elements for which we haven't yet found the next greater element. The stack helps in maintaining order and efficiently finding the next greater number.

2. Iterate with Circular Array Logic: Since the array is circular, any element's next greater number could be ahead of it or wrapped around back to the start of the array. To simulate this without actually duplicating the array, iterate through the array twice (virtually making it 2n long).

3. Maintain Decreasing Order in Stack: As you iterate through each element:

   • If the stack is not empty and the current element is greater than the element corresponding to the index at the top of the stack, then the current element is the next greater element for the elements at the stack's indices. Pop these indices from the stack and assign the current element as their next greater number.
   • Push the current index onto the stack. This action ensures that if there isn’t yet a next greater number found for the current element, we'll keep checking for it in subsequent iterations.

4. Handling No Next Greater Element: After processing all elements, any indices left in the stack do not have a next greater number. Hence, assign -1 to these elements.

Example Walkthrough

• Consider nums = [1,2,1]. We help visualize the process:

  • First, look at the first element 1. Since there’s nothing in our stack, simply push its index 0.
  • Next, observe 2. It is greater than 1 (from the top index of the stack), so 1's next greater number is 2. Pop index 0 from the stack and push index 1.
  • Now at the second 1, it's not greater than 2. Push its index 2. For the circular effect, repeat looking from start.
  • As we see element 1 again in the virtual extended iteration, 2 again appears to be the next greater number for the second 1.

In this way, we maintain efficiency and ensure each element is processed in relation to its circular position within the array.

Solutions

public class Solution {
    
    public int[] findNextGreaterElements(int[] array) {
        int[] result = new int[array.length];
        Stack<Integer> indices = new Stack<>();
        for (int index = 2 * array.length - 1; index >= 0; --index) {
            while (!indices.isEmpty() && array[indices.peek()] <= array[index % array.length]) {
                indices.pop();
            }
            result[index % array.length] = indices.isEmpty() ? -1 : array[indices.peek()];
            indices.push(index % array.length);
        }
        return result;
    }
}