Next Greater Element I Easy 0 attempts
LeetCode ↗

Next Greater Element I

Easy Stack&Queue LeetCode

You're given two arrays, nums1 and nums2, where every element of nums1 also appears somewhere in nums2. For each value in nums1, locate that same value's position in nums2 and find the first element to its right that is larger — this is its "next greater element." If no larger element follows it in nums2, use -1 instead.

Input Format
Implement nextGreaterElement(nums1, nums2). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums1 = [2]
nums2 = [2,1]
Output
[-1]
Constraints
  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All values in nums1 and nums2 are unique
Test Cases (2)
Case 1
Args: [[4,1,2],[1,3,4,2]] Expected: [-1,3,-1]
Case 2
Args: [[2],[2,1]] Expected: [-1]
Topics
Stack&Queue

Monotonic Stack + Hash Map

javascript
function nextGreaterElement(nums1, nums2) {
  const map = new Map(), stack = [];
  for (const n of nums2) {
    while (stack.length && stack[stack.length-1] < n) map.set(stack.pop(), n);
    stack.push(n);
  }
  return nums1.map(n => map.get(n) ?? -1);
}

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

Saved in this browser only. Private to you.

JavaScript