medium Next Greater Element II

Problem Statement

Given a circular integer array nums, return the array containing the next greater number for each element in nums.

A next greater number of a number num is the first greater number than the current number in its traversing-order in the array, which means you could search circularly to find its next greater number. If the next greater element doesn't exist, return -1 for the particular number number.

Examples

• Example 1:

  • Input: nums = [2, 1, 2, 4, 3]
  • Expected Output: [4, 2, 4, -1, 4]
  • Justification: For 2, the next greater number is 4. For 1, it's 2 (the next number in the array). For the second 2, 4 is again the next greater. For 4, there's no greater number, hence -1. For 3, looping over, 4 is the next greater number.

• Example 2:

  • Input: nums = [1, 5, 3, 6, 4]
  • Expected Output: [5, 6, 6, -1, 5]
  • Justification: The next greater for 1 is 5, for 5 is 6, for 3 is 6 again, and for 6 there's no greater number (-1). For 4, considering the circular nature, 5 is the next greater number.

• Example 3:

  • Input: nums = [9, 8, 7, 3, 2, 1, 6]
  • Expected Output: [-1, 9, 9, 6, 6, 6, 9]
  • Justification: For 9, as it's the greatest, no number is greater, so -1. For 8 and 7, 9 is the next greater number. For 3, 2, and 1, the next greater number is 6, considering the circular array. For 6, 9 is the next greater number by looping over.

Solution

To solve this problem, we'll employ a stack to keep track of the indices of elements for which we're trying to find the next greater number. We loop through the array twice to simulate the circular nature of the problem. This ensures that for every element, we get a chance to check the rest of the array and then loop back to check the elements before it, if necessary.

Our approach works because, with the stack, we maintain elements in decreasing order from top to bottom. This way, when we encounter an element greater than the stack's top, we know we've found the next greater element for the indices stored in the stack. By looping twice, we ensure every element is considered in its circular context, making the approach effective for finding the next greater element in a circular array.

Step-by-Step Algorithm

1. Initialize an empty stack to keep track of indices whose next greater element hasn't been found yet.
2. Create an array result with the same length as the input array nums, filled with -1. This array will store the next greater element for each position in nums.
3. Loop through the array twice (to account for the circular nature of the problem) using an index variable i that goes from 0 to 2 * len(nums) - 1. The actual index for accessing elements in nums will be i % len(nums) due to the circular nature.
4. In each iteration of the loop, do the following:
   • Use the current index i % len(nums) to access the element in nums.
   • While the stack is not empty and the current element is greater than the element at the index at the top of the stack:
     • Pop the index from the top of the stack.
     • Update the result array at the popped index with the current element, indicating the next greater element has been found.
   • If the loop is in its first iteration through nums (i.e., i < len(nums)), push the current index i % len(nums) onto the stack.
5. After completing the loop, return the result array, which now contains the next greater element for each position in the input array nums.

Algorithm Walkthrough

Let's consider the input [9, 8, 7, 3, 2, 1, 6].

• Initial State:
  • nums = [9, 8, 7, 3, 2, 1, 6]
  • result = [-1, -1, -1, -1, -1, -1, -1] (Assuming no greater element found yet)
  • stack = [] (Empty)

First Pass:

• Step 1: Index 0, Element 9
  • Add 0 to the stack. stack = [0]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 2: Index 1, Element 8
  • Add 1 to the stack. stack = [0, 1]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 3: Index 2, Element 7
  • Add 2 to the stack. stack = [0, 1, 2]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 4: Index 3, Element 3
  • Add 3 to the stack. stack = [0, 1, 2, 3]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 5: Index 4, Element 2
  • Add 4 to the stack. stack = [0, 1, 2, 3, 4]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 6: Index 5, Element 1
  • Add 5 to the stack. stack = [0, 1, 2, 3, 4, 5]
  • result = [-1, -1, -1, -1, -1, -1, -1]
• Step 7: Index 6, Element 6
  • Since 6 is greater than 1, 2, and 3. Update their positions in result.
  • Pop 5, 4, and 3 from stack, and update result for these indices.
  • stack = [0, 1, 2, 6]
  • result = [-1, -1, -1, 6, 6, 6, -1]
• Step 8: Index i % 7 = 7 % 7 = 0, Element 9
  • Since 9 is greater than 6, 8, and 7. Update their positions in result.
  • Pop 6, 2, and 1 from stack, and update result for these indices.
  • stack = [0]
  • result = [-1, 9, 9, 6, 6, 6, 9]
• Continue iterating the array in the second pass.

Final State:

• result = [-1, 9, 9, 6, 6, 6, -1]

Code

public class Solution {

  // Function to find the next greater element for each element in the circular array
  public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n]; // Result array
    java.util.Stack<Integer> stack = new java.util.Stack<>(); // Stack to keep track of indices
    java.util.Arrays.fill(result, -1); // Initialize result array with -1

    for (int i = 0; i < n * 2; i++) {
      int num = nums[i % n]; // Current number (use modulo for circular array)
      // Find next greater element
      while (!stack.isEmpty() && nums[stack.peek()] < num) {
        result[stack.pop()] = num; // Update result for the index popped from the stack
      }
      if (i < n) stack.push(i); // Push current index to stack
    }

    return result; // Return the result array
  }

  // Main method to test the solution
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    int[] example1 = { 2, 1, 2, 4, 3 };
    int[] example2 = { 1, 5, 3, 6, 4 };
    int[] example3 = { 9, 8, 7, 3, 2, 1, 6 };
    // Print results
    System.out.println(
      java.util.Arrays.toString(solution.nextGreaterElements(example1))
    );
    System.out.println(
      java.util.Arrays.toString(solution.nextGreaterElements(example2))
    );
    System.out.println(
      java.util.Arrays.toString(solution.nextGreaterElements(example3))
    );
  }
}

Complexity Analysis

• Time Complexity: , where n is the number of elements in the array. Each element is processed at most twice - once when added to the stack and once when removed.
• Space Complexity: for the stack and the result array. The stack can grow up to the size of the input array in the worst case.