Back to Problems

Next Greater Element I

Easy
monotonic-stack

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

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

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Key Insight: Use a monotonic decreasing stack on nums2. When we pop an element, we have found its next greater element. Store results in a hash map for O(1) lookup when processing nums1.

Example 1

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: For 4: no greater element exists. For 1: next greater is 3. For 2: no greater element after it.

Example 2

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: For 2: next greater is 3. For 4: no greater element exists.

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
Show Hints (4)
Hint 1: What data structure allows us to efficiently track elements waiting for a greater element?
Hint 2: A stack can hold elements in decreasing order. When we see a larger element, we pop all smaller ones.
Hint 3: For each popped element, the current element is its next greater element.
Hint 4: Use a hash map to store the next greater element for each value in nums2, then look up answers for nums1.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?