LeetCode #217 Contains Duplicate Solution & Explanation - Zyrastory

Content

Post Views: 800

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.

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(n²) ➡ 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

LeetCode #217 JavaScript 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

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

Latest Post

LeetCode #1598 Crawler Log Folder Solution & Explanation2024-08-27
LeetCode #374 Guess Number Higher or Lower Solution & Explanation2024-05-21
LeetCode #349 Intersection of Two Arrays Solution & Explanation2024-05-16
LeetCode #506 Relative Ranks Solution & Explanation2024-05-08
LeetCode #292 Nim Game Solution & Explanation2024-05-07

LeetCode Problem

Solution

C# Solution

Java Solution

Python3 Solution

JavaScript Solution

Submission Detail

Conclusion

Related Posts

LeetCode #1291 Sequential Digits Solution & Explanation

LeetCode #100 Same Tree Solution & Explanation

Leave a ReplyCancel Reply