Next Greater Element in Circular Array

Problem Statement

Given a circular integer array arr[], the task is to determine the next greater element (NGE) for each element in the array.

The next greater element of an element arr[i] is the first element that is greater than arr[i] when traversing circularly. If no such element exists, return -1 for that position.

Circular Property:

Since the array is circular, after reaching the last element, the search continues from the beginning until we have looked at all elements once.

Examples:

Input: arr[] = [1, 3, 2, 4]
Output: [3, 4, 4, -1]
Explanation:
The next greater element for 1 is 3.
The next greater element for 3 is 4.
The next greater element for 2 is 4.
The next greater element for 4 does not exist, so return -1.

Input: arr[] = [0, 2, 3, 1, 1]
Output: [2, 3, -1, 2, 2]
Explanation:
The next greater element for 0 is 2.
The next greater element for 2 is 3.
The next greater element for 3 does not exist, so return -1.
The next greater element for 1 is 2 (from circular traversal).
The next greater element for 1 is 2 (from circular traversal).

Constraints:

1 ≤ arr.size() ≤ 10^5
0 ≤ arr[i] ≤ 10^6

Intuition

To find the next greater element for each value in a circular array, we need to determine, for each number, the next number in traversal order that is strictly greater than it.

We use a stack to keep track of the indices of elements for which we haven't yet found a next greater element. When we encounter a new number, we compare it with the elements indexed at the top of the stack:

If the current number is greater than the one at the stack's top, then it's the "next greater element" for that previous number — we pop and record the result.

We repeat this until we can't find more matches or the stack is empty.

Since the array is circular, we iterate from 0 to 2 * n - 1 and use index % n to simulate wrapping around.

Important note: We only push indices less than n into the stack to avoid redundant processing in the second half (which is just to simulate the circular nature).

Steps

1. Check for null or empty input and return an empty list if so.

2. Initialize a stack for indices and an integer array result of length n.

3. Loop i from 0 to 2*n – 1:

• Let j = i % n.

• While the stack is not empty and arr[stack.peek()] < arr[j], pop an index and set result[pop] = arr[j].

• If i < n, push j onto the stack.

1. After the loop, any indices still in the stack have no next greater element; set their result entry to -1.

2. Convert result into an ArrayList and return it.

Complexity

Time: O(n) — each element is pushed and popped at most once over the 2n iterations.

Space: O(n) — for the stack and the result array/list.

Code

class Solution {
    public ArrayList<Integer> nextLargerElement(int[] arr) {
        // code here
        if (arr == null || arr.length == 0) {
            return new ArrayList<>();
        }
        int length = arr.length;
        Stack<Integer> stack = new Stack<>();
        int [] result = new int [length];
        for (int index = 0; index < length * 2; index++) {
            while (!stack.isEmpty() && arr[stack.peek() % length] < arr[index % length]) {
                int currentIndex = stack.pop();
                result[currentIndex % length] = arr[index % length];
            }
            if (index < length)
                stack.push(index);
        }
        while (!stack.isEmpty()) {
            result[stack.pop() % length] = -1;
        }
        ArrayList<Integer> resultList = new ArrayList<>();
        for (int num : result) {
            resultList.add(num);
        }
        return resultList;
    }
}