217. Contains Duplicate
Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 56.9%
Problem Breakdown
The problem asks us to determine if there are any duplicate elements in an integer array nums. The input is a list of integers, and the output should be a boolean value: true if there is at least one duplicate, and false if all elements are distinct. The constraints specify that the length of the array can range from 1 to (10^5), and each element can be as large as (10^9) or as small as (-10^9).
Intuition
A brute-force approach would involve checking every pair of elements in the array to see if they are equal. This would have a time complexity of (O(n^2)), which is inefficient given the constraints. The key insight is that we can use a hash table (or set) to track the elements we’ve seen so far, allowing us to detect duplicates in linear time.
Approach
- Initialize a Set: Use a set to keep track of unique elements encountered as we iterate through the array.
- Iterate Through the Array: For each element in the array:
- Check if the element is already in the set.
- If it is, return
truebecause a duplicate has been found. - If it is not, add the element to the set.
- If it is, return
- Check if the element is already in the set.
- Return False: If the loop completes without finding any duplicates, return
false.
This approach leverages the average (O(1)) time complexity for insertions and lookups in a hash table, resulting in an overall time complexity of (O(n)).
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the number of elements in the array. We iterate through the array once, and each insertion and lookup operation in the set takes average (O(1)) time.
- Space Complexity: (O(n)), in the worst case, when all elements are unique and stored in the set.
Solution
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Edge Cases Handled
- Empty Array: The function will correctly return
falsebecause there are no elements to compare. - Single Element: The function will correctly return
falsefor a single-element array since there can’t be duplicates. - All Elements Unique: The function will return
falseas expected when all elements in the array are distinct. - All Elements Duplicates: The function will return
trueimmediately upon encountering the first duplicate element.