Next Greater Element I

EasyStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two arrays of distinct integers, nums1 and nums2, where every value of nums1 also appears in nums2. For a value x in nums2, its next greater element is the first value to the right of x in nums2 that is strictly larger than x, or -1 if there is none. For each nums1[i], look up that value in nums2 and report its next greater element. Return an array ans of the same length as nums1, in the same order. Aim for O(nums1.length + nums2.length) time.

Examples

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Nothing right of 4 is larger; 3 is the first value larger than 1; nothing right of 2 exists.
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
3 follows 2 and is larger; 4 is the last element.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All values in nums1 are distinct, and all values in nums2 are distinct
  • Every value in nums1 also appears in nums2

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems