faster solution when findNums.size() << nums.size() (with explanations)

• The top-voted solutions find the next greater element for all elements in `nums`, but actually we just need to do this for elements in `findNums`. The reason why these solutions are faster is because `nums.size() < 1000`, which is quite small. If `nums.size()` is very large and `findNums.size() << nums.size()`, my solution would be faster.

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
unordered_map<int, int> hash; // the indices of elements in findNums
vector<int> res(findNums.size(), -1);
stack<int> s; // visited elements in findNums for which we don't know the next greater element
for(int i = 0; i < findNums.size(); ++i){
hash[findNums[i]] = i;
}
s.push(numeric_limits<int>::max()); // a dummy value to avoid checking whether s is empty
for(int cur : nums){
while(cur > s.top()){
res[hash[s.top()]] = cur;
s.pop();
}
if(hash.count(cur)) s.push(cur); // s only contains the elements in findNums
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.