496. Next Greater Element I

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # time O(N+M), M = len(nums1), N = len(nums2) space O(N)
        # step1: create a stack, a hashmap
        st = []
        d = {}
        # step2: store number in decreasing order
        for num in nums2:
             # step2.1 pop the smaller numbers off stack before appending next bigger number, hence store next bigger in dictionary 
            while st and st[-1] < num:
                d[st.pop()] = num
            st.append(num)

        size = len(nums1)
        # step3: loop through nums2, check if hashmap have next bigger number saved, if not,assigned -1
        # optimization: instead of creating a res to save next greater number, store it in place 
        for i in range(size):
            nums1[i] = d.get(nums1[i],-1)
        return nums1