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.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
The problem asks to determine if an array contains duplicate elements. Two efficient solutions exist: sorting and using a hash table (or set).
Approach: This approach leverages the fact that after sorting, duplicate elements will be adjacent to each other.
Sort the array: We sort the input array nums
in ascending order. This step allows duplicate numbers to cluster together.
Linear scan for duplicates: After sorting, we iterate through the sorted array. If any two consecutive elements are identical, we've found a duplicate and return true
. If the iteration completes without finding duplicates, we return false
.
Code (Python):
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort() # Sort the array in place
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return True # Found a duplicate
return False # No duplicates found
Time Complexity: O(n log n) due to the sorting algorithm. The linear scan is O(n), but it's dominated by the sorting time complexity.
Space Complexity: O(1) in-place sorting (most implementations use constant extra space). Some sorting algorithms might use O(log n) space in the worst case, but in practice, this is generally constant.
Approach: This method uses a hash table (or a set in many languages) to efficiently track seen elements.
Initialize a set: Create an empty set (or hash set) to store numbers encountered so far.
Iterate and check: Iterate through the array nums
. For each number, check if it's already present in the set. If it is, we've found a duplicate, and return true
. Otherwise, add the number to the set.
No duplicates: If the loop completes without finding any duplicates, return false
.
Code (Python):
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set() # Use a set for efficient lookups
for num in nums:
if num in seen:
return True # Duplicate found
seen.add(num)
return False # No duplicates found
Time Complexity: O(n) because we iterate through the array once. Set lookups (num in seen
) are on average O(1) in hash tables.
Space Complexity: O(n) in the worst case, as the set could potentially store all unique elements from the input array.
| Feature | Sorting | Hash Table | |----------------|--------------------|--------------------| | Time Complexity | O(n log n) | O(n) | | Space Complexity| O(1) (typically) | O(n) |
The hash table approach is generally preferred because it provides linear time complexity, making it significantly faster for larger input arrays. However, the sorting approach might be preferable if space complexity is a major constraint and the input array is relatively small. Many languages provide efficient set implementations that optimize hash table operations.