Next Greater Element I — LeetCode 496 Python Solution

The problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

Example

Input

nums1 = [4,1,2], nums2 = [1,3,4,2]

Output

[-1,3,-1]

Explanation

The next greater element for each value of nums1 is as follows:

Python solution

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stk = []
        d = {}
        for x in nums2[::-1]:
            while stk and stk[-1] < x:
                stk.pop()
            if stk:
                d[x] = stk[-1]
            stk.append(x)
        return [d.get(x, -1) for x in nums1]

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 496. Next Greater Element I is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems