Next Greater Element I

Intuition

Solution

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        mapping = {}
        for i in range(len(nums2) - 1, -1, -1):
            ng = -1
            j = i + 1
            while j != -1 and j < len(nums2):
                if nums2[j] > nums2[i]:
                    ng = j
                    break
                else:
                    j = mapping[nums2[j]]
            mapping[nums2[i]] = ng
        ans = []
        for i in nums1:
            if mapping[i] == -1:
                ans.append(-1)
            else:
                ans.append(nums2[mapping[i]])
        return ans