Next Greater Element in Circular Array

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Extend the array conceptually by doubling it.

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?