Solution 1 - Brute Force

For each element in nums1, find it in nums2, then scan to the right in nums2 for the first element greater than it. If no greater element is found, return -1 for that position.

TimeComplexity: O(n \cdot m)

SpaceComplexity: O(1)

""" 0496.1 - Next Greater Element I - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Next Greater Element Function"""
        result = []

        for num in nums1:
            found = False
            greater = -1
            for n in nums2:
                if n == num:
                    found = True
                elif found and n > num:
                    greater = n
                    break
            result.append(greater)

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))  # [-1, 3, -1]
    print(Solution().nextGreaterElement([2, 4], [1, 2, 3, 4]))     # [3, -1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Monotonic Stack with Hash Map

Iterate through nums2 and use a monotonic decreasing stack. For each element, while it is greater than the top of the stack, pop from the stack and record the current element as the next greater element in a hash map. Then look up results for each element in nums1.

TimeComplexity: O(n + m)

SpaceComplexity: O(n)

""" 0496.2 - Next Greater Element I - Solution 2 - Monotonic Stack with Hash Map """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Next Greater Element Function"""
        next_greater = {}
        stack = []

        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)

        return [next_greater.get(num, -1) for num in nums1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))  # [-1, 3, -1]
    print(Solution().nextGreaterElement([2, 4], [1, 2, 3, 4]))     # [3, -1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0496 - Next Greater Element I

Solution 1 - Brute Force

Solution 2 - Monotonic Stack with Hash Map