Write next_greater_element(nums1: list[int], nums2: list[int]) -> list[int].
All values in nums2 are distinct, and every value of nums1 also appears in nums2. For each x in nums1, find where x sits in nums2 and return the first value to its right in nums2 that is larger than x, or -1 if there is none. Answers come back in the order of nums1.
Example: nums1 = [6, 1, 8], nums2 = [1, 6, 2, 8] gives [8, 6, -1].
nums1 = [2], nums2 = [2, 1] gives [-1].
Constraints: 1 <= len(nums1) <= len(nums2) <= 10^5.
Searching nums2 separately for each query, even just with nums2.index(x), is O(n²) and fails the large test. Aim for O(n).
Show hint
answer every value of nums2 in a single left-to-right pass, keeping the values still waiting for something larger, and store the answers in a dict for the lookups.