386. Next Greater Element I
Your function receives two integer arrays, nums1 and nums2. All values in nums2 are distinct, and every element of nums1 also appears somewhere in nums2.
For an element x sitting at some position in nums2, its next greater element is the first value strictly larger than x that appears to its right in nums2. If nothing to the right is larger, the next greater element is -1.
For each x in nums1, find x inside nums2 and report its next greater element there. Return the answers as an array ans with ans[i] corresponding to nums1[i], in the same order as nums1.
Example 1:
Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: In nums2, the 4 has only a 2 after it, so its answer is -1. The 1 is immediately followed by 3, which is larger. The 2 is the last element, so nothing follows it: -1.
Example 2:
Input: nums1 = [2, 4], nums2 = [1, 2, 3, 4]
Output: [3, -1]
Explanation: After the 2 in nums2 the first larger value is 3. The 4 sits at the end, so its answer is -1.
Constraints:
- 1 ≤ nums1.length ≤ nums2.length ≤ 1000
- 0 ≤ nums1[i], nums2[i] ≤ 10⁴
- All values in nums2 are distinct
- Every element of nums1 also appears in nums2
Hints:
The direct way: for each element of nums1, find it in nums2 and scan rightward until something bigger shows up. That is O(n1 · n2) — fine here, but there is a one-pass idea worth learning.
Walk nums2 once keeping a stack of values that are still waiting for their next greater element. When a new value x arrives, every stacked value smaller than x has just found its answer: pop them, record value → x in a hash map, then push x. The stack stays decreasing from bottom to top.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Expected output: [-1, 3, -1]