LeetCode #217 Contains Duplicate Solution & Explanation

LeetCode Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

LeetCode #217 Examples and Constraints

Solution

This problem is to find out is there any duplicate element in array, it seems very easy, let’s give a try.

C# Solution

Solution1 – IndexOf  (Not Recommend – too slow)

In our first try, let’s use a simple iteration, and uses 【Array.IndexOf】 function.

If it return any index ( not found will return -1), than return true ( there have duplicate element in array ).

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        for(int i = 0;i<nums.Length;i++)
        {
            if(Array.IndexOf(nums, nums[i],i+1)!=-1)
            {
                return true;
            }
        }
        return false;
    }
}

Runtime : 889ms、1045ms、980ms ≈ Faster than 10~15% …

Time Complexity : O(n2) ➡ Array.IndexOf ≈ O(n) * For Iteration O(n)

Solution2 – HashSet

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> hSet = new HashSet<int>();
        
        for(int i = 0;i<nums.Length;i++)
        {
            if(hSet.Contains(nums[i]))
            {
                return true;
                
            }
            hSet.Add(nums[i]);
        }
        return false;
    }
}

Runtime : 197ms、244ms、187ms ≈ Faster than 70~90%

Time Complexity : O(n) ➡ HashSet.Contains ≈ O(1) * For Iteration O(n)

Solution3

There is another solution, which is to use the Array.Sort function to make nums sorted.

Then, we can iterate through the array and check if any element is the same as the next element. If there are any such elements, we can conclude that there are duplicate elements in the array.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums);
        
        for(int i = 0;i<nums.Length-1;i++)
        {
            if(nums[i]==nums[i+1])
            {
                return true;
            }
        }
        return false;
    }
}

Runtime : 294ms、283ms、311ms

Java Solution

Solution1 – HashSet

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hSet = new HashSet<Integer>();
        
        for(int i = 0;i<nums.length;i++)
        {
            if(hSet.contains(nums[i]))
            {
                return true;
            }
            hSet.add(nums[i]);
        }
        return false;
    }
}

Runtime : 9ms、6ms、11ms

Solution2 – Arrays.sort

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        
        for(int i = 0;i<nums.length-1;i++)
        {
            if(nums[i]==nums[i+1])
            {
                return true;
            }
        }
        return false;
    }
}

Runtime : 28ms、24ms、30ms ≈ Faster than 15~25%

Python3 Solution

Solution1 – set

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s = set()
        
        for i in range(len(nums)):
            if(nums[i] in s):
                return True
            s.add(nums[i])
            
        return False

Runtime : 510ms、487ms、455ms

Solution1.1 – Dictionary can achieve the same effect

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        d = {}  #dict
        
        for i in range(len(nums)):
            if(nums[i] in d):
                return True
            d[nums[i]] = 0
            
        return False

Solution2 – sort the list first

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        
        for i in range(len(nums)-1):
            if(nums[i] == nums[i+1]):
                return True
            
        return False

Runtime : 760ms、959ms、654ms

JavaScript Solution

Solution1 – set

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    var set = new Set();
    for(var i = 0;i<nums.length;i++)
    {
        if(set.has(nums[i]))
        {
            return true;
        }
        set.add(nums[i]);
    }
    return false;
};

Runtime : 73ms、116ms、114ms

Solution2 – sort the list first

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for(var i=0; i<nums.length-1;i++)
    {
        if(nums[i] == nums[i+1]) 
        {
            return true;
        }
    }
    return false;
};

Submission Detail


Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot !

If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : Contains Duplicate – LeetCode

Similar Question :  LeetCode #219 Contains Duplicate II Solution & Explanation

Reference : HashSet.Contains – Time Complexity – stackoverflow Official document

Latest Post

Leave a Reply

Your email address will not be published. Required fields are marked *