{x}
blog image

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.

 

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: 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.

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

 

Constraints:

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

Solution Explanation: Next Greater Element II

This problem asks to find the next greater element for each element in a circular integer array. A circular array means the element after the last element is the first element. If no greater element exists, we return -1.

The most efficient approach uses a monotonic stack. A monotonic stack is a stack that maintains a specific order (increasing or decreasing). In this case, we'll use a decreasing monotonic stack.

Algorithm:

  1. Initialization: Create an array ans of the same size as nums, initialized with -1. This array will store the next greater element for each index. Also, initialize an empty stack stk.

  2. Iteration: Iterate through the nums array twice (to handle the circularity). We iterate backward from 2*n - 1 to 0, where n is the length of nums. This backward iteration simplifies finding the "next" greater element. The modulo operator (%) ensures we wrap around the array correctly.

  3. Stack Operations: For each element nums[j] (where j = i % n):

    • Pop smaller elements: While the stack is not empty and the top element of the stack (stk[-1]) is less than or equal to nums[j], pop elements from the stack. This ensures that the stack always contains decreasing elements.
    • Assign next greater element: If the stack is not empty after popping, the top element of the stack is the next greater element for nums[j]. Assign this value to ans[j].
    • Push current element: Push nums[j] onto the stack.

  4. Return: Return the ans array.

Time Complexity: O(n). Each element is pushed and popped at most once onto the stack.

Space Complexity: O(n) in the worst case, as the stack could potentially hold all the elements of nums.

Code Examples (Python and Java):

Python:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        stk = []
        for i in range(n * 2 - 1, -1, -1):
            j = i % n
            while stk and stk[-1] <= nums[j]:
                stk.pop()
            if stk:
                ans[j] = stk[-1]
            stk.append(nums[j])
        return ans

Java:

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

The other languages (C++, Go, TypeScript, JavaScript) follow a very similar structure, using their respective stack implementations. The core logic remains the same: a decreasing monotonic stack to efficiently find the next greater element in a circular array.