Next Greater Element II LeetCode Solution

Table of Contents

Problem Statement

Next Greater Element II LeetCode Solution – 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 <= 10⁴
-10⁹ <= nums[i] <= 10⁹

Approach

Idea:

first, we find the maxEleIdx in the array
now this problem is the same as the next greater element 1
we traverse from maxEleIdx to 0 then in circular way n-1 to maxEleIdx+1.
to find the next greater element in the array we maintain a monotonically increasing stack
to do this we traverse the nums array from (maxEleIdx to 0 then in circular way n-1 to maxEleIdx+1)
if the stack is not empty, then compare its top element with nums[i],if the nums[i] is greater than the stack’s top element, then we pop from the stack while (!st.empty() && st.top()>=nums[i] )
now if we find an element in the stack then we store it at ans[idx]
otherwise, we store -1 at ans[idx]
now we push nums[i] into the stack as it might be the next greater element for the remaining elements

Code

C++ Program of Next Greater Element II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int maxEleIdx=0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>=nums[maxEleIdx])
            {
                maxEleIdx=i;
            }
        }
        int n=nums.size();
        stack<int> st;  
        vector<int> ans(n);
        int idx=maxEleIdx;   
        for(int i=0;i<nums.size();i++)
        {
            while(!st.empty() && st.top()<=nums[idx])
                st.pop();
            
            if(st.empty())
            {
                ans[idx]=-1;
            }
            else
            {
                ans[idx]=st.top();
            }
            
            st.push(nums[idx]);
            
            idx--;
            
            if(idx<0)
                idx=nums.size()-1;
        }  
        return ans;
        
    }
};

Java Program of Next Greater Element II

class Solution {
    public int[] nextGreaterElements(int[] nums) { 
        int maxEleIdx=0,n=nums.length;
        for(int i=1;i<nums.length;i++)
        {
            if(nums[i]>=nums[maxEleIdx])
            {
                maxEleIdx=i;
            }
        }
        
         int ans[]=new int[nums.length];
        
        int idx=maxEleIdx;
        Stack<Integer> st=new Stack<>();
        
        for(int i=0;i<nums.length;i++)
        {
            while(!st.isEmpty() && st.peek()<=nums[idx])
                st.pop();
            
            if(st.isEmpty())
            {
                ans[idx]=-1;
            }
            else
            {
                ans[idx]=st.peek();
            }
            
            st.push(nums[idx]);
            
            idx--;
            
            if(idx<0)
                idx=nums.length-1;
        }
        return ans;
    }
}

Complexity Analysis for Next Greater Element II LeetCode Solution

Time Complexity

The time complexity of the above code is O(2*n) because we are traversing the array two times.

Space Complexity

The space complexity of the above code is O(n) because we are using the ans array to store the next greater element of every element