LeetCode - Contains Duplicate-CodePudding

I am learning DSA and I've been trying to solve the LeetCode Prob which is "contains duplicate" https://leetcode.com/problems/contains-duplicate/

I have couple of approach and it seems to be working fine but on Submit, LeetCode throws an error saying "Time Limit Exceeded".

I know this is because it consumes more time than expected. Please help me to get optimal approach.

public boolean containsDuplicate(int[] nums) {
        if(nums.length>0){
        for(int i=0;i<nums.length;i  ){
            for(int j=i 1;j<nums.length;j  ){
                if(nums[i]==nums[j]){
                    return true;
                }
            }
        }
        }
        return false;
        
    }

 public boolean containsDuplicate(int[] nums) {
        boolean set = true;
        int count = 0;
        if(nums.length>0){
        for(int i=0;i<nums.length;i  ){
            for(int j=i 1;j<nums.length;j  ){
                if(nums[i]==nums[j]){
                    count  ;
                    break;
                }
            }
        }
        }
       if(count>0){
           set = true;
       }
       else{
           set = false;
       }
        return set;
    }

CodePudding user response：

This approach will be faster - use unordered_set is a little bit faster (30ms) (translated from earlier Python code)


class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> rec;
        for (auto& n : nums) {
            if (rec.find(n) != rec.end()) {
                return true;
            }
            rec.insert(n);
        }
        return false;
    }
};

CodePudding user response：

If you execute

for(int i=0;i<nums.length;i  ){
    for(int j=i 1;j<nums.length;j  ){
        if(nums[i]==nums[j]){
            count  ;
            break;
        }
    }
}

you are basically getting O(n²), since you are running nested for loops that iterate through all of your input. For an input of very big size, your implementation takes more time than accepted to finish.

This problem requires you to use a data structure that can quickly tell you if an element is already there or not. If you don't know what structure is this, try to find it. I'll write the answer as an spoiler so you can see if you don't find.

The structure you want is a HashSet. HashSets can store elements in constant time and they can tell you if an element exists or not in constant time. Simply create a HashSet, add all elements there one by one and for each element you add, ask if the HashSet already contains it.