Anubhav Shukla

Posted on

# Leetcode 217. Contains Duplicate. DSA - #4

## 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

return False
``````

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

## Best Approach using Hashing (one liner)

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