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.
LeetCode Solutions1 <= nums.length <= 105-109 <= nums[i] <= 109In the worst case, we have to compare each element with every other element in the array.
The brute force approach does not use any additional data structures that grow with the input size.
The brute force approach uses two nested loops to compare each element with every other element in the array. If it finds any two elements that are the same, it returns true. If it finishes checking all pairs without finding any duplicates, it returns false.
In the worst case, we may have to check each element in the array once.
In the worst case, we may need to store all elements in the set.
The hash set approach uses a set data structure to keep track of the numbers we have seen as we iterate through the array. For each number, we check if it is already in the set. If it is, we return true, indicating that a duplicate has been found. If it is not in the set, we add it to the set and continue iterating. If we finish iterating through the array without finding any duplicates, we return false.
The sorting step takes time, and the subsequent iteration takes time.
In the worst case, the sorting algorithm may require space, depending on the implementation. However, if an in-place sorting algorithm is used, the space complexity can be reduced to .
The sorting approach first sorts the array, which brings any duplicate elements next to each other. Then, it iterates through the sorted array and checks for adjacent duplicates. If it finds any two adjacent elements that are the same, it returns true. If it finishes iterating through the array without finding any duplicates, it returns false.
We iterate through the array once to create the set, and then compare lengths, which is overall.
In the worst case, we may need to store all elements in the set.
This approach creates a set from the input array, which automatically removes any duplicate elements. Then, it compares the length of the original array with the length of the set. If they are different, it means that there were duplicates in the original array, and we return true. If they are the same, it means that all elements were distinct, and we return false.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Brute Force | No extra space needed | Very slow for large inputs | |||
| Hash Set | Linear time, can exit early when duplicate found | Requires extra space for the set | |||
| Sorting | Simple adjacent comparison after sorting | Slower than hash-based approaches, may modify input | |||
| Hash Set Length Comparison | Most concise — single line of code, leverages built-in Set | Cannot exit early, always processes entire array |
The optimal approach for this problem is Solution 4: Hash Set Length Comparison, which achieves time complexity and space complexity. It is the most concise solution — simply comparing the length of the original array with a Set created from it — making it extremely readable and easy to implement.
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: # Check each element against every other element for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] == nums[j]: return True
return Falseclass Solution: def containsDuplicate(self, nums: List[int]) -> bool: # create a set to store seen numbers seen = set()
for num in nums: if num in seen: return True
seen.add(num)
return Falseclass Solution: def containsDuplicate(self, nums: List[int]) -> bool: nums.sort()
# Iterate through the sorted array and check for adjacent duplicates for i in range(1, len(nums)): if nums[i] == nums[i - 1]: return True
return Falseclass Solution: def containsDuplicate(self, nums: List[int]) -> bool: # comparing the length of the original list with the length of the set created from the list return len(nums) != len(set(nums))