Leetcode 217. Contains Duplicate. DSA - #4

Question Link

Python || C++ || TypeScript

Brute Force Approach

This approach is very simple, so I am not going to waste much time in this approach

• We take one element and compare it with all the other elements.
• We do this for all the elements.

Code

def containsDuplicateMethod1(nums: list[int]) -> bool:
    length = len(nums)
    for i in range(length):
        for j in range(i + 1, length):
            if nums[i] == nums[j]:
                return True
    return False

Time Complexity: O(n^2)
Space Complexity: O(1)

Better Approach using Sorting

Since we have to find the duplicate elements, so we can sort the array and then find the duplicate elements.
Duplicate elements will be adjacent to each other.

For example: nums = [1, 2, 3, 1]

After sorting: nums = [1, 1, 2, 3]

Now we can find the duplicate elements by comparing the adjacent elements.

Code

def containsDuplicateMethod2(nums: list[int]) -> bool:
    nums.sort()
    length = len(nums)
    for i in range(length - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

Time Complexity: O(nlogn)
Space Complexity: O(1)

Best Approach using Hashing

This method is also very easy to understand.

• We create a Set.
• We traverse the array and check if the element is present in the Set or not.
• If the element is present in the Set then we return True.
• If the element is not present in the Set then we add the element in the Set.
• If we traverse the whole array, and we don't find any duplicate element then we return False.

Code

def containsDuplicateMethod3(nums: list[int]) -> bool:
    storage = set()
    for value in nums:
        if value in storage:
            return True
        storage.add(value)

    return False

Time Complexity: O(n)
Space Complexity: O(n)

Bonus

Best Approach using Hashing (one liner)

def containsDuplicateMethod4(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))