Question: Next Greater Element I
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.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Problem Breakdown:
Before we dive into the code, let's break down the problem and understand what's expected:
We have two arrays,
nums1
andnums2
, of non-negative integers.Each element in
nums1
is present innums2
.For each element in
nums1
, we need to find the next greater element innums2
.If there is no greater element in
nums2
, we should return-1
for that element in the result array.
Approach:
To solve this problem efficiently, we can use a stack and a hash map. Here's the step-by-step approach:
We initialize an empty stack
s
and an empty unorderd_mapmp
.We traverse through
nums2
, which serves as our parent array to find the next greater elements.In each iteration, we compare the current element,
it
, with the top element of the stack (s.top()
). Ifit
is greater, we update the hash mapmp
with the mapping of the top element of the stack toit
. We also pop the top element from the stack because we have found the next greater element for it.After processing
nums2
, we have a complete mapping of each element to its next greater element inmp
.We initialize the result vector
res
with the same size asnums1
, filled with -1.We iterate through
nums1
and check if the element exists inmp
. If it does, we update the corresponding position inres
with the next greater element found inmp
.Finally, we return the
res
vector, which contains the next greater elements for each element innums1
.
Code:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> mp;
stack<int> s;
for(auto it : nums2){
while(!s.empty() && s.top() < it){
mp[s.top()] = it;
s.pop();
}
s.push(it);
}
vector<int> res(nums1.size(),-1);
for(int i = 0; i < nums1.size(); ++i){
if(mp[nums1[i]]){
res[i] = mp[nums1[i]];
}
}
return res;
}
Time and Space Complexity:
Let's analyze the time and space complexity of our solution:
Time Complexity: The solution processes both
nums1
andnums2
exactly once, so the time complexity is O(N1 + N2), where N1 is the length ofnums1
, and N2 is the length ofnums2
.Space Complexity: We use a stack and a hash map to store intermediate results. The space complexity is O(N2) in the worst case, where N2 is the length of
nums2
.
Top comments (0)