Code Implementation

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        res = [-1] * n
        stack = []
        for i in range(2 * n):
            num = nums[i % n]
            while stack and nums[stack[-1]] < num:
                res[stack.pop()] = num
            if i < n:
                stack.append(i)
        return res
      

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;
        for (int i = 0; i < 2 * n; ++i) {
            int num = nums[i % n];
            while (!st.empty() && nums[st.top()] < num) {
                res[st.top()] = num;
                st.pop();
            }
            if (i < n) st.push(i);
        }
        return res;
    }
};
      

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

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < 2 * n; ++i) {
        let num = nums[i % n];
        while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
            res[stack.pop()] = num;
        }
        if (i < n) stack.push(i);
    }
    return res;
};
      

Problem Description

You are given a circular array of integers called nums. For each element in nums, you need to find the next greater element, which is the first element to its right in the array (considering the array as circular) that is strictly greater than it. If there is no such element, return -1 for that position.

The array is circular, meaning after the last element, you continue from the beginning. Each element's "next" can wrap around. You must not reuse elements out of order, and there is only one correct next greater element (or -1) for each position.

Constraints:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

Thought Process

At first glance, you might consider checking for each element in nums by looping through all subsequent elements (wrapping around if needed) to find the next greater element. However, this brute-force method would require examining up to n-1 elements for each position, leading to a time complexity of O(n^2). For large arrays, this is inefficient.

To improve, we recall the "Next Greater Element" problem for a linear array, which can be efficiently solved using a stack. The stack keeps track of indices whose next greater element hasn't been found yet. By iterating through the array twice (to simulate circularity), we can ensure each element gets a fair chance to find its next greater element, while still maintaining efficiency.

The key insight is to use a monotonic stack to hold indices of elements for which we haven't yet found a next greater number, and to traverse the array twice to account for the circular nature.

Solution Approach

Let's break down the optimized solution step by step:

1. Initialize the result array: Create an array res of the same length as nums, filled with -1. This will hold the next greater element for each index.
2. Use a stack to track indices: The stack will keep the indices of elements whose next greater element hasn't been found yet.
3. Iterate through the array twice: To simulate the circular nature, loop from 0 to 2n - 1 (where n is the length of nums). For each iteration, compute the real index as i % n.
4. Process the stack: For each number, check if it is greater than the number at the index on top of the stack. If so, this is the next greater element for that index; update res accordingly and pop the index from the stack. Repeat until the top of the stack is not less than the current number or the stack is empty.
5. Push indices during the first pass: Only push indices onto the stack during the first n iterations (i.e., i < n), because after that, we're only simulating the circularity and don't need to push new indices.
6. Return the result: After the loop, res contains the next greater elements for each position, or -1 if none exists.

This approach efficiently finds the next greater elements in O(n) time and space.

Example Walkthrough

Let's walk through an example with nums = [1, 2, 1]:

• Initialize res = [-1, -1, -1] and stack = [].
• First Pass (i = 0 to 2):
  • i = 0: num = 1. Stack is empty. Push 0 to stack. Stack = [0].
  • i = 1: num = 2. nums[stack[-1]] = nums[0] = 1 < 2. Pop 0, set res[0] = 2. Stack = []. Push 1. Stack = [1].
  • i = 2: num = 1. nums[stack[-1]] = nums[1] = 2 > 1. Push 2. Stack = [1,2].
• Second Pass (i = 3 to 5):
  • i = 3: num = 1 (nums[0]). Stack = [1,2]. nums[stack[-1]] = nums[2] = 1 = 1. No pop. Continue.
  • i = 4: num = 2 (nums[1]). nums[stack[-1]] = nums[2] = 1 < 2. Pop 2, set res[2] = 2. Stack = [1]. nums[stack[-1]] = nums[1] = 2 = 2. No pop. Continue.
  • i = 5: num = 1 (nums[2]). Stack = [1]. nums[stack[-1]] = nums[1] = 2 > 1. No pop. Continue.
• Final result: res = [2, -1, 2]

Each element's next greater element is found by leveraging the stack and the circular pass.

Time and Space Complexity

Brute-force approach: For each element, you may need to scan up to n-1 elements, resulting in O(n^2) time complexity. Space is O(n) for the result.

Optimized stack approach: Each index is pushed and popped from the stack at most once, so the total time complexity is O(n). Space complexity is also O(n) for the result array and the stack.

Summary

The Next Greater Element II problem leverages the concept of a monotonic stack to efficiently solve a problem that would otherwise require quadratic time. By simulating the circular array with a double pass and judiciously using a stack to track unresolved indices, we ensure that each element is processed quickly and only as needed. This approach is both elegant and practical, making it a valuable technique for similar array problems.