496. Next Greater Element I

/*
Refer: https://leetcode.com/problems/next-greater-element-i/discuss/97595/Java-10-lines-linear-time-complexity-O(n)-with-explanation

Time Complexity: O(M + N)
Space Complexity:
    Without result space: O(N)
    With result space: O(M + N)

M = length of nums1
N = length of nums2
*/
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) throws IllegalArgumentException {
        if (nums1 == null || nums2 == null) {
            throw new IllegalArgumentException("Input array is null");
        }

        Map<Integer, Integer> map = new HashMap();
        Stack<Integer> stack = new Stack();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] result = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }

        return result;
    }
}