# 496. Next Greater Element I

You are given two arrays **(without duplicates)** `nums1` and `nums2` where `nums1`’s elements are 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, output -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.
```

**Note:**\\

1. All elements in `nums1` and `nums2` are unique.
2. The length of both `nums1` and `nums2` would not exceed 1000.

```cpp
// Brute Force
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // time: O(m * n); space: O(m), m: nums1 size, n: nums2 size
    vector<int> res(nums1.size());
    for (int i = 0; i < nums1.size(); ++i) {
        int j = 0, k = 0;
        for (; j < nums2.size(); ++j) {
            if (nums2[j] == nums1[i]) break;
        }
        for (k = j + 1; k < nums2.size(); ++k) {
            if (nums2[k] > nums1[i]) {
                res[i] = nums2[k];
                break;
            }
        }
        if (k == nums2.size()) res[i] = -1;
    }
    return res;
}
```

```cpp
// Hashmap
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // time: O(m * n); space: O(m + n)
    int m = nums1.size(), n = nums2.size();
    vector<int> res(m, -1);
    unordered_map<int, int> mp; // record the corresponding position
    for (int i = 0; i < n; ++i) mp[nums2[i]] = i;
    for (int i = 0; i < m; ++i) {
        int start_idx = mp[nums1[i]];
        for (int j = start_idx + 1; j < n; ++j) {
            if (nums2[j] > nums1[i]) {
                res[i] = nums2[j];
                break;
            }
        }
    }
    return res;
}
```

```cpp
// Hashmap + Stack
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // time: O(m + n); space: O(m + n)
    vector<int> res;
    unordered_map<int, int> mp; // record the first larger number
    stack<int> st;
    for (int num : nums2) {
        while (!st.empty() && st.top() < num) {
            mp[st.top()] = num;
            st.pop();
        }
        st.push(num);
    }
    for (int num : nums1) {
        res.push_back(mp.count(num) ? mp[num] : -1);
    }
    return res;
}
```
