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