Next Greater Element I

Intuition

The heavy work is finding the next greater element for each value in nums2; the nums1 lookups are trivial afterward. Maintain a stack of values that are still waiting for a greater neighbor. As you scan left to right, any time the current value beats the value on top of the stack, the current value is exactly that top's next greater element. Pop every element the current value exceeds and record the mapping. Because each value is pushed and popped at most once, the entire scan is linear. Finally, look up each nums1 value in the map, defaulting to -1.

Algorithm walkthrough

1. 1Create an empty stack and an empty hash map from value to its next greater value.
2. 2Iterate through nums2. For each value cur, while the stack is non-empty and cur is greater than the top, pop the top and record map[top] = cur.
3. 3Push cur onto the stack; it now waits for its own next greater element.
4. 4Any values left on the stack at the end have no greater element to their right, so they simply stay absent from the map.
5. 5Build the result by mapping each element of nums1 through the map, using -1 when the value is missing.

Implementation

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        next_greater = {}
        stack = []
        for cur in nums2:
            while stack and cur > stack[-1]:
                next_greater[stack.pop()] = cur
            stack.append(cur)
        return [next_greater.get(x, -1) for x in nums1]