Next Greater Element I

Given two arrays nums1 and nums2, where nums1 is a subset of nums2, return an array answer such that answer[i] is the next greater element of nums1[i] in nums2. If it does not exist, put -1. Example: Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: For 4 there is no greater element to its right in nums2; for 1 it is 3. Pattern focus: Next Greater Pattern with a monotonic stack and a lookup map.

Input Format

nums1 = query array, nums2 = reference array

Output Format

next greater element in nums2 for each value in nums1

Constraints

  • 1 <= nums1.length <= nums2.length <= 10^4
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All values of nums1 are unique and are present in nums2

Examples

Example 1:

Input:

nums1 = [4,1,2]
nums2 = [1,3,4,2]

Output:

[-1,3,-1]

Explanation:

Compute next greater values for nums2 first, then answer nums1 queries.

Example 2:

Input:

nums1 = [2,4]
nums2 = [1,2,3,4]

Output:

[3,-1]

Explanation:

The lookup map lets you answer each query in O(1).

Loading...
Next Greater Element I - Monotonic Stack Queue