Using counting array (C++, 36 ms, better than 83%)


  • 0
    J

    We cant declare a counting array from INT_MIN to INT_MAX due to memory restrictions, so first find the max and min of the array. Time complexity is O(N)

    bool containsDuplicate(vector<int>& nums) {
            if(nums.size()<2)
                return false;
            else{
                int min=INT_MAX,max=INT_MIN;
                for(int i=0; i<nums.size(); i++){
                    if(nums[i]>max)
                        max = nums[i];
                    if(nums[i]<min)
                        min = nums[i];
                } 
                vector<int> array(max-min+1);
                for(int i=0; i<nums.size(); i++){
                if(array[nums[i]-min]==1)
                    return true;
                else 
                    array[nums[i]-min]=1;
                }
                return false;
            }
        }

Log in to reply
 

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