Next Greater Element I

The key idea

Precompute the next greater element for every value in nums2 in one left-to-right pass using a stack that stays decreasing. When a new value is larger than the stack's top, that value IS the answer for the top, so pop and record it. Store the answers in a hash map keyed by value, then look up each nums1[i] in O(1).

Problem

You are given two distinct-valued integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each value in nums1, find its next greater element in nums2. The next greater element of a value x is the first number to the right of x (in nums2) that is strictly greater than x. If no such number exists, the answer for that value is -1.

Return an array ans of the same length as nums1, where ans[i] is the next greater element of nums1[i] as described above.

Constraints

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.

Examples

Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1]

Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1]

Complexity

Time: O(n + m) Space: O(m)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →