Why is O(nlogn) solution faster than the O(n)?


  • -1
    M
    bool containsDuplicate(vector<int>& nums) {
            //O(n) space and time
            unordered_map<int,int> table;
            for(vector<int>::iterator it = nums.begin();it<nums.end();it++){
                unordered_map<int,int>::iterator temp = table.find(*it);
                if(temp!=table.end()){
                    temp->second += 1;
                    if(temp->second >=2){
                        return true;
                    }
                }else{
                    table.insert({*it,1});
                }
            }
            
            return false;
    }
    
    bool containsDuplicate(vector<int>& nums) {
            //O(nlogn) space and time
    int size = nums.size();
            if(size>1){
                sort(nums.begin(), nums.end());
                for(int i=0; i<size; ++i)
                    if(nums[i] == nums[i+1] && i+1 != size)
                        return true;
            }
            return false;
        }
    

    O(n) solution gave 52 ms but O(nlogn) 40 ms


  • 0
    M

    @mshshetty056 Update : Is this because hash table may not hash all the elements spread across different buckets due to which the find() will have constant complexity and linear in worst case (all elements in same bucket) ?


  • 0

    @mshshetty056 Format your code with ``` please. this is really a hard job to read your code.


  • 1
    class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) 
        {
            unordered_map<int, int> count_map;
            for(auto n: nums) if(count_map[n]++ == 1) return true;
            return false;
        }
    };
    

    Indeed, I just tested using the code above. I suppose the higher-level object in C++ will take much more underlying operations to support its feature in this case when the number is rather sparse then the sorting method will be much stable and quicker.


Log in to reply
 

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