nums 1 is a subset of nums 2. For each number in nums 1, find the first greater number to its right in nums 2, or minus 1.
DSA Animator › DSA Revision › Stack › Next Greater Element I
Remember: one monotonic stack pass finds the next greater element for everything. A hash map answers the queries afterwards. The video solves Next Greater Element I (LeetCode 496, Easy) with the Monotonic Stack pattern from the Stack topic, and you can replay every step in the interactive Next Greater Element I animation.
nums 1 is a subset of nums 2. For each number in nums 1, find the first greater number to its right in nums 2, or minus 1.
For nums 1 equal to 4, 1, 2, and nums 2 equal to 1, 3, 4, 2, the answer is minus 1, 3, minus 1.
Searching nums 2 for each number and scanning right is O of n times m. Instead, compute the next greater element for all of nums 2 once.
Walk through nums 2 with a decreasing stack. When a bigger number arrives, it is the next greater element for everything smaller on the stack. Store those answers in a hash map, then look up each number of nums 1.
Push 1. 3 is bigger, so 1 maps to 3, then push 3. 4 is bigger, so 3 maps to 4, then push 4. 2 is smaller, so push it. 4 and 2 never meet a bigger number, so they map to minus 1. For nums 1: 4 gives minus 1, 1 gives 3, and 2 gives minus 1.
In code, loop over nums 2. While the stack top is smaller than the current number, pop it and map it to the current number. Push the current number. Then fill the answer with map lookups, defaulting to minus 1, so it's O of n plus m time.
Remember: one monotonic stack pass finds the next greater element for everything. A hash map answers the queries afterwards.