Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number. For example, if nums = [1,2,1], the output should be [2,-1,2]. The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2. As another example, if nums = [1,2,3,4,3], the output should be [2,3,4,-1,4]. How would you implement a function to efficiently solve this problem?

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];

            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                result[stack.pop()] = num;
            }

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

        return result;
    }
}

Brute Force Solution

For each element, iterate through the rest of the array (wrapping around if necessary) to find the next greater element.

import java.util.Arrays;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < i + n + 1; j++) {
                if (nums[j % n] > nums[i]) {
                    result[i] = nums[j % n];
                    break;
                }
            }
        }

        return result;
    }
}

Optimal Solution

Use a stack to keep track of indices of elements for which we have not yet found the next greater element. Iterate through the array twice to simulate the circular nature.

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];

            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                result[stack.pop()] = num;
            }

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

        return result;
    }
}

Big(O) Run-time Analysis

Brute Force Solution:

• For each element in nums, we iterate through the array (potentially twice in the circular case).
• Thus, the time complexity is O(n^2), where n is the length of the array.

Optimal Solution:

• We iterate through the array at most twice (2n).
• Each element is pushed onto the stack once and popped at most once.
• Therefore, the time complexity is O(n).

Big(O) Space Usage Analysis

Brute Force Solution:

• We use an additional array result of size n to store the next greater elements.
• The space complexity is O(n).

Optimal Solution:

• We use an additional array result of size n to store the next greater elements.
• We also use a stack which, in the worst case, can contain all the elements of nums.
• Therefore, the space complexity is O(n).

Edge Cases

1. Empty array:
   • If the input array is empty, return an empty array.
2. Array with one element:
   • If the input array has only one element, the next greater element is -1.
3. Array with all elements the same:
   • If all elements are the same, the next greater element for all elements is -1.
4. Array in descending order:
   • If the array is in descending order, the next greater element for all elements is -1.
5. Array in ascending order:
   • If the array is in ascending order, the next greater element for the last element is -1, and for the rest, it's the next element in the array.