Problem Description
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 index i in nums1, 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 where ans[i] is the next greater element as described above.
Key Insights
- We need to find the next greater element for each element in nums1 as it appears in nums2.
- We can utilize a stack to keep track of elements for which we haven't found the next greater element yet.
- A hash map can be used to store the next greater elements for efficient look-up.
Space and Time Complexity
Time Complexity: O(nums1.length + nums2.length)
Space Complexity: O(nums2.length)
Solution
To solve the problem, we can use a monotonic stack to keep track of elements in nums2 as we traverse it. The idea is to iterate through nums2 from right to left. For each element, we will pop elements from the stack until we find one that is greater than the current element. If we find such an element, it is the next greater element for the current element. We store the result in a hash map for quick access later. Finally, we create the result array for nums1 by looking up each element in the hash map.