# Next Greater Element II LeetCode Solution

Difficulty Level Medium
MindTickle Walmart Global techViews 84

## 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`), 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`4
• `-10`9` <= nums[i] <= 10`9

## Approach

### Idea:

1. first, we find the maxEleIdx in the array
2. now this problem is the same as the next greater element 1
3. we traverse from maxEleIdx to 0 then in circular way n-1 to maxEleIdx+1.
4. to find the next greater element in the array we maintain a monotonically increasing stack
5. to do this we traverse the nums array from (maxEleIdx to 0  then in circular way n-1 to maxEleIdx+1)
6. 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] )
7.  now if we find an element in the stack then we store it at ans[idx]
otherwise, we store -1 at ans[idx]
8.  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

1. ```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

Translate »