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


  • 0
    L

    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;
        }
    };
    

Log in to reply
 

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