Easy

Next Greater Element I

LAB

For each value in nums1, return its next greater value to the right in nums2, or -1 if none exists.

EXAMPLES

Example 1

Input
{
  "nums1": [
    4,
    1,
    2
  ],
  "nums2": [
    1,
    3,
    4,
    2
  ]
}

Output
[
  -1,
  3,
  -1
]

FUNCTION SHAPE

nums1: intArraynums2: intArray→intArray

SOLUTION NOTE

Direct application of the next greater template with index mapping.

Reveal reference solution +

pythonREFERENCE

def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    def ng(A):
        n = len(A)
        stack = []
        res = [n] * n
        for i in range(n):
            while stack and A[stack[-1]] < A[i]:
                res[stack[-1]] = i
                stack.pop()
            stack.append(i)
        return res

    idx_map = {v:i for i,v in enumerate(nums2)}
    NG = ng(nums2)
    res = [-1] * len(nums1)

    for i in range(len(nums1)):
        idx = NG[idx_map[nums1[i]]]
        if idx != len(nums2):
            res[i] = nums2[idx]
    return res

TimeO(n + m)

SpaceO(n)

Open on LeetCode ↗