# Next Greater Element I Leetcode Solution

Difficulty: Easy HotstarViews 89

## Problem Statement

Next Greater Element I Leetcode Solution – The next greater element of some element `x` in an array is the first greater element that is to the right of `x` in the same array.

You are given two distinct 0-indexed integer arrays `nums1` and `nums2`, where `nums1` is a subset of `nums2`.

For each `0 <= i < nums1.length`, find the index `j` such that `nums1[i] == nums2[j]` and determine the next greater element of `nums2[j]` in `nums2`. If there is no next greater element, then the answer for this query is `-1`.

Return an array `ans` of length `nums1.length` such that `ans[i]` is the next greater element as described above.

Example 1:

Input:

``` nums1 = [4,1,2], nums2 = [1,3,4,2]
```

Output:

``` [-1,3,-1]
```

Explanation:

``` The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
```

Example 2:

Input:

``` nums1 = [2,4], nums2 = [1,2,3,4]
```

Output:

``` [3,-1]
```

Explanation:

``` The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
```

Constraints:

• `1 <= nums1.length <= nums2.length <= 1000`
• `0 <= nums1[i], nums2[i] <= 10`4
• All integers in `nums1` and `nums2` are unique.
• All the integers of `nums1` also, appear in `nums2`.

Follow up: Could you find an `O(nums1.length + nums2.length)` solution?

## Approach

### Idea:

1. we make a map to store every element’s next greater element
2. to find the next greater element in nums2 we maintain a monotonically increasing stack
3.  to do this we traverse the nums2 array from (n-1 to 0    where n is the size of nums2)
4. if the stack is not empty, then compare its top element with nums2[i]
5.  if the nums2[i] is greater than stack’s top element, then we pop from stack while (!st.empty() && st.top()>nums2[i] )
6.  now if we find an element in the stack then we store it in the map
otherwise, we store -1 in the map
7.  now we push nums2[i] into the stack as it might be the next greater element for elements ranges b/w (i-1 to 0) ### C++ Program of  Next Greater Element I

```class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

map<int,int> mp;
stack<int> st;

for(int i=nums2.size()-1;i>=0;i--)
{
while(!st.empty() && st.top()<nums2[i])
st.pop();

if(st.empty())
mp[nums2[i]]=-1;
else
mp[nums2[i]]=st.top();

st.push(nums2[i]);

}

for(int i=0;i<nums1.size();i++)
{
nums1[i]=mp[nums1[i]];
}

return nums1;

}
};```

### Java Program of  Next Greater Element I

```class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> mp = new HashMap<>();

Stack<Integer> st = new Stack<>();

for (int i=nums2.length-1;i>=0;i--) {

while (!st.isEmpty() && st.peek() < nums2[i])
st.pop();

if(st.isEmpty())
{
mp.put(nums2[i],-1);
}
else
{
mp.put(nums2[i],st.peek());
}

st.push(nums2[i]);
}
for (int i = 0; i < nums1.length; i++)
nums1[i] = mp.getOrDefault(nums1[i], -1);
return nums1;
}
}

```

## Complexity Analysis for Next Greater Element I Leetcode Solution

### Time Complexity

O(n+m) where n is the size of nums1 and m is the size of nums2

### Space Complexity

O(m) as we use a map to store every element’s next element and stack to find the next greater element

Translate »