Solution 1 - Hash Set

Iterate through the array and insert each element into a hash set. Before inserting, check if the element already exists in the set. If it does, a duplicate has been found — return True. If the loop completes without finding any duplicates, return False.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0217.1 - Contains Duplicate - Solution 1 - Hash Set """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def containsDuplicate(self, nums: List[int]) -> bool:
        """Contains Duplicate Function"""
        seen = set()

        for num in nums:
            if num in seen:
                return True
            seen.add(num)

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().containsDuplicate([1, 2, 3, 1]))       # True
    print(Solution().containsDuplicate([1, 2, 3, 4]))       # False
    print(Solution().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))  # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Sorting

Sort the array first so that any duplicate elements become adjacent. Then iterate through the sorted array and check if any two consecutive elements are equal. If so, return True. Otherwise, return False.

TimeComplexity: O(n \log n)

SpaceComplexity: O(1)

""" 0217.2 - Contains Duplicate - Solution 2 - Sorting """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def containsDuplicate(self, nums: List[int]) -> bool:
        """Contains Duplicate Function"""
        nums.sort()

        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().containsDuplicate([1, 2, 3, 1]))       # True
    print(Solution().containsDuplicate([1, 2, 3, 4]))       # False
    print(Solution().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))  # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Set Length Comparison

Convert the entire array to a set, which removes duplicates. Compare the length of the set with the length of the original array. If they differ, duplicates exist.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0217.3 - Contains Duplicate - Solution 3 - Set Length Comparison """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def containsDuplicate(self, nums: List[int]) -> bool:
        """Contains Duplicate Function"""
        return len(nums) != len(set(nums))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().containsDuplicate([1, 2, 3, 1]))       # True
    print(Solution().containsDuplicate([1, 2, 3, 4]))       # False
    print(Solution().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))  # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0217 - Contains Duplicate

Solution 1 - Hash Set

Solution 2 - Sorting

Solution 3 - Set Length Comparison