# Next Greater Element I

You are given two integer arrays `nums1` and `nums2` both of unique elements, where `nums1` is a subset of `nums2`. Find all the next greater numbers for `nums1`‘s elements in the corresponding places of `nums2`. The Next Greater Number of a number `x` in `nums1` is the first greater number to its right in `nums2`. If it does not exist, return `-1` for this number.

Example 1:

```Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.```

Example 2:

```Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.```

Constraints:

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

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element `x` is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Examples:
i.   For an array, the rightmost element always has the next greater element as -1.
ii.  For an array that is sorted in decreasing order, all elements have the next greater element as -1.
iii. For the input array `{1,4,3,6,7}` the next greater elements for each element are as follows.

Algorithm :

1. Iterate over the array `arr[]` for `i = 0 to (arr.length -1 )`.
1. If the `Stack` is empty then push the element in the `Stack`.
2. Else if the `Stack` is not empty and `Stack` top is less than the current element `arr[i].`
1. `NGE` found for the current `Stack` top. The current element is greater than `Stack` top.
2. Print (`stack.pop()` and `arr[i]`). Remember `stack.pop()` will remove the current top.
3. Repeat 4 and 5 for next Stack Top. All the elements present in the `Stack` are on the left side of the current element in the input array. And if the current element is greater than stack entries then current element is the `NGE`.
4. Push the current element in the `Stack`.
2. At these step elements left in the `Stack`, do not have any `NGE`.
```class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {

Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for(int i = nums2.length-1 ; i >= 0 ; i--){
int num = nums2[i];
while(!stack.isEmpty() && num > stack.peek()){
stack.pop();
}
int next_greater = stack.isEmpty() ? -1 : stack.peek();
stack.push(num);
map.put(num, next_greater);
}
int[] result = new int[nums1.length];
int j = 0;
for(int num : nums1){
result[j] = map.get(num);
j++;
}
return result;
}
}
```

Complexity Analysis:

• Time Complexity : `O(m+n)`. The entire `nums` array(of size `n`) is scanned only once. The stack’s `n` elements are popped only once.
• Space Complexity : `O(m+n)``stack` and `map` of size `n` is used. `result` array of size `m` is used but output is not considered in complexcity.

Categories: Stack