class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Stack<Integer> stack = new Stack<Integer>();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        for (int i = nums2.length - 1; i >= 0; i--) {
            // get rid of all stack numbers that are smaller
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                stack.pop();
            }

            int nextGreater;
            if (stack.isEmpty()) {
                nextGreater = -1;
            }
            else {
                // the top of the stack will contain the number that is greater,
                // since by this point all smaller ones would have been removed
                nextGreater = stack.peek();
            }
            hashMap.put(nums2[i], nextGreater);

            stack.push(nums2[i]);
        }

        for (int i = 0; i < nums1.length; i++) {
            ans[i] = hashMap.get(nums1[i]);
        }

        return ans;
    }
}