496. Next Greater Element I

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	Create a mapping of nums1 elements to indices. For each element in nums2, if it exists in nums1, scan rightward to find the next greater element using nested loops.	\(O(n × m)\)	\(O(n)\)
Stack	Use a monotonic decreasing stack to track elements awaiting their next greater element. When a larger element is found, pop from stack and update results for all smaller elements.	\(O(n + m)\)	\(O(n)\)

Implementation

PythonJavaScriptGo

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n2i = {
            num: i
            for i, num in enumerate(nums1)
        }
        result = [-1] * len(nums1)
        for i in range(len(nums2)):
            if nums2[i] not in n2i:
                continue
            for j in range(i+1, len(nums2)):
                if nums2[j] > nums2[i]:
                    idx = n2i[nums2[i]]
                    result[idx] = nums2[j]
                    break
        return result

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n2i = {
            num: i
            for i, num in enumerate(nums1)
        }
        result = [-1] * len(nums1)
        stack = []
        for i in range(len(nums2)):
            current = nums2[i]
            while len(stack) != 0 and current > stack[-1]:
                idx = n2i[stack.pop()]
                result[idx] = current
            if current in n2i:
                stack.append(current)
        return result