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]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class NextGreaterElementI {
    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        int[] NGE = nextGreaterElement(nums1, nums2);
        System.out.println(Arrays.toString(NGE));
    }

    static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        List<Integer> v = new ArrayList<Integer>();
        Stack<Integer> st = new Stack<Integer>();
        int n = nums2.length;
        int m = nums1.length;
        if (n == 0 || m == 0)
            return null;
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        st.push(nums2[n - 1]);
        mp.put(nums2[n - 1], -1);
        for (int i = n - 2; i >= 0; i--) {
            // while stack is not empty and stack top is
            // less than current value then pop from
            // stack
            while (!st.isEmpty() && st.peek() <= nums2[i]) {
                st.pop();
            }

            // if stack is empty then add -1
            if (st.isEmpty()) {
                mp.put(nums2[i], -1);
            }

            // else add stack top element
            else
                mp.put(nums2[i], st.peek());

            // push current element into the stack
            st.push(nums2[i]);
        }

        for (int i = 0; i < m; i++)
            v.add(mp.get(nums1[i]));
        return v.stream().mapToInt(Integer::intValue).toArray();
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> nextGreaterElement(vector<int> &nums1, 
         vector<int> &nums2)
{
    vector<int> v;
    stack<int> st;
    int n = nums2.size();
    int m = nums1.size();
    if (n == 0 || m == 0)
        return v;
    map<int, int> mp;
    st.push(nums2[n - 1]);
    mp[nums2[n - 1]] = -1;
    for (int i = n - 2; i >= 0; i--)
    {
        //while stack is not empty and stack top is
        //less than current value then pop from 
        //stack
        while (!st.empty() && st.top() <= nums2[i])
            st.pop();

        //if stack is empty then add -1
        if (st.empty())
            mp[nums2[i]] = -1;

        //else add stack top element
        else
            mp[nums2[i]] = st.top();

        //push current element into the stack
        st.push(nums2[i]);
    }

    for (int i = 0; i < m; i++)
        v.push_back(mp[nums1[i]]);
    return v;
}

int main()
{
    vector<int> nums1 = {4, 1, 2};
    vector<int> nums2 = {1, 3, 4, 2};
    vector<int> NGE = nextGreaterElement(nums1, nums2);
    cout << "[";
    for (int i = 0; i < NGE.size() - 1; i++)
        cout << NGE[i] << ",";
    cout << NGE[NGE.size() - 1] << "]";

    return 0;
}