Leetcode 496 -- Next Greater Element I.py

# Leetcode 496: Next Greater Element I
# https://leetcode.com/problems/next-greater-element-i/

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = [-1] * len(nums1)
        stack = []
        seen = {}

        # Step 1: Store the index of elements from nums1 in seen
        for i in range(len(nums1)):
            seen[nums1[i]] = i

        # Step 2: Iterate through nums2 to find the next greater element for each number
        for num in nums2:
            # Step 3: While the stack is not empty and the current number is greater than the stack's top element
            while stack and num > stack[-1]:
                # Step 4: If this number is in nums1, assign it as the next greater element
                if stack[-1] in seen:
                    answer[seen[stack[-1]]] = num
                stack.pop()  # Remove the element from the stack

            # Step 5: Add the current number to the stack
            stack.append(num)

        return answer

#time complexity: O(N+M)
#space complexity: O(N+M)