In this Leetcode Next Greater Element I problem solution 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.
Problem solution in Python.
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
next_greatest = {}
for i in range(len(nums2)):
while len(stack) > 0 and stack[-1][0] < nums2[i]:
val, index = stack.pop()
next_greatest[val] = nums2[i]
stack.append((nums2[i], i))
result = []
for i in range(len(nums1)):
if nums1[i] in next_greatest:
result.append(next_greatest[nums1[i]])
else:
result.append(-1)
return result
Problem solution in Java.
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
next_greatest = {}
for i in range(len(nums2)):
while len(stack) > 0 and stack[-1][0] < nums2[i]:
val, index = stack.pop()
next_greatest[val] = nums2[i]
stack.append((nums2[i], i))
result = []
for i in range(len(nums1)):
if nums1[i] in next_greatest:
result.append(next_greatest[nums1[i]])
else:
result.append(-1)
return result
Problem solution in C++.
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
map<int,int> dict;
int n = nums2.size();
int m = nums1.size();
for(int i=0;i<n;i++)
{
dict[nums2[i]] = i;
}
stack<pair<int,int>> s;
vector<int> greater(n,-1);
for(int i=0;i<n;i++)
{
pair<int,int> p;
while(!s.empty() && s.top().first < nums2[i])
{
p = s.top();
s.pop();
greater[p.second] = nums2[i];
}
p.first = nums2[i];
p.second = i;
s.push(p);
}
vector<int> ans(m,-1);
for(int i=0;i<m;i++)
{
ans[i] = greater[dict[nums1[i]]];
}
return ans;
}
};