Next Greater Element II

Share

Given a circular integer array nums, return the next greater number for every element. In a circular array, the next greater number of the last element is the first element that is greater.

Example 1
Input: [1,2,1] → Output: [2,-1,2]
Example 2
Input: [1,2,3,4,3] → Output: [2,3,4,-1,4]

Solution Approach

Use a monotonic stack with indices. Simulate the circular array by iterating twice (0 to 2n-1) using modulo. Only push indices during the first pass.

  • Initialize result[] with -1.
  • Iterate i from 0 to 2n-1, use idx = i%n.
  • While stack non-empty and nums[stack.peek()] < nums[idx]: result[pop] = nums[idx].
  • Only push index if i < n (first pass).
Java
import java.util.*;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!stack.isEmpty() && nums[stack.peek()] < nums[idx])
                result[stack.pop()] = nums[idx];
            if (i < n) stack.push(idx);
        }
        return result;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)