two C++ Solution run time with explanation


  • 6
    1. run time O(n) space O(n) use unordered_map
      First loop through all elements and count each number appearance. Then loop through unordered_map, to find if the key - 1 is in the unordered map. If key - 1 and key both in the map, update the result
        int findLHS(vector<int>& nums) {
            unordered_map<int,int>m;
            for(auto i: nums)
                m[i]++;
            int res = 0;
            for(auto it:m)
                if(m.count(it.first-1)>0)
                    res = max(res, it.second+m[it.first-1]);
            return res;
        }
    
    1. O(nlogn) running time ,space O(1) using sort
      The idea is to loop through each elements and update the result. The start position is used for counting purpose and new start is used for whenever come across different number

    When the number is different from previous number, update the new start position. When difference between current position and start position is bigger than 1 then update start position.

           int findLHS(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            int len = 0;
            for(int i = 1, start = 0, new_start = 0; i<nums.size(); i++)
            {
    
                if (nums[i] - nums[start] > 1)    
                    start = new_start;
                if (nums[i] != nums[i-1]) 
                    new_start = i;
                if(nums[i] - nums[start] == 1)
                    len = max(len, i-start+1);
            }
            return len;
    

  • 0
    N

    Can anyone tell me what's the difference between m.count(it.first-1)>0 and m[it.first-1]>0?
    The result is wrong if I use m[it.first-1]>0.


  • 1

    @npath
    Basically, When you use m.count(it.first-1)>0, it just search if the key in the it and if not it will not generate a new key and insert into unordered map. But when you use m[it.first-1]>0, then if it.first-1 is not as key in the unordered map, it will generate a new key as it.first-1 and insert into the unordered map.

    So m.count(it.first-1)>0 is slight more efficient as for memory.


  • 0
    N

    @beckswu Your explanation is a big help.Thank you!


Log in to reply
 

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