Next Greater Element in Circular Array

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Extend the array conceptually by doubling it. Use monotone stack. For circular array, simulate double traversal.

Algorithm

1Traverse array twice (0 to 2n-1) using index % n.
2Monotone stack. For i in second pass: pop stack elements smaller than current, assign result.
3First pass builds stack; second pass resolves remaining.

Common Pitfalls

•Only assign result on first n elements. Traverse 2n times to handle circular wrap.

Next Greater Element in Circular Array.java

Java

// Approach: Monotonic stack on doubled array (or two passes). For each element find first greater to its right circularly.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> nextLargerElement(int[] nums) {
        int n = nums.length;
        ArrayList<Integer> res = new ArrayList<>(Collections.nCopies(n, -1));
        Stack<Integer> stack = new Stack<>(); // Store indices

        // Loop through twice to simulate circular array
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];

            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                int idx = stack.pop();
                res.set(idx, num);
            }

            if (i < n)
                stack.push(i);
        }

        return res;
    }
}

Was this solution helpful?