Next Greater Element I

Problem Summary

• For two arrays nums1 and nums2, where nums1 is a subset of nums2
• Find next greater element for each number in nums1 from nums2, if not found have -1
• Return result which is of equal length to nums1 with next greater element from nums2

Main Concepts Used

• Monotonic Stack

Time & Space Complexity

• Time: $O(n+m)$ → Reason: Iterating through each input array once
• Space: $O(n)$ → Reason: Hashmap equal to length of nums1

Code

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        result = [-1] * len(nums1)
        hashmap = {}
        for i, num in enumerate(nums1):
            hashmap[num] = i
        for num in nums2:
            while stack and num > stack[-1]:
                foundNextGreaterFor = stack.pop()
                # we found the next greater item for foundNextGreaterFor value
                result[hashmap[foundNextGreaterFor]] = num
            if num in hashmap:
                stack.append(num)
        return result

Common Mistakes / Things I Got Stuck On

• Trying to use Increasing Monotonic Stack instead of decreasing