why My O(nlogn) soloution faster than O(n) soloution
Kunal Gupta
77

Time complexity of this code is O(nlogn)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n-1; i++)
            if(nums[i] == nums[i+1])
                return true;
        return false;
    }
};

while time complexity of below code is O(n) still below one comes slower as below one is 55% faster than other soloution while above one is 82% faster than other soloution How?

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,bool> mpp;
        for(int i=0;i<nums.size();i++){
            if(mpp[nums[i]]==true) return true;
            mpp[nums[i]]=true;
        }
        return false;
    }
};

question link https://leetcode.com/problems/contains-duplicate/

Comments (3)