217: Contains Duplicate Problem - Quick Reference
Problem Statement:
Given an integer array `nums[]`, return `True` if any value appears at least twice, and `False` if every
element is distinct.
Example:
Input: [1, 2, 3, 1] - Output: True
Input: [1, 2, 3] - Output: False
Approach:
Optimal (Hashing): Use a set to track elements and check for duplicates in O(n) time complexity.
Algorithm Steps:
1. Initialize an empty set `seen`.
2. Iterate through the array.
3. If element in `seen`, return `True`.
4. Add element to `seen`.
5. Return `False` if no duplicates.
Time Complexity:
Optimal: O(n)
Brute Force: O(n²) (nested loops to compare every pair)
Space Complexity:
Optimal: O(n) (due to the set)
Brute Force: O(1) (no extra space used)
Edge Cases:
- Empty array [] - Return False
- Single element [1] - Return False
- All identical [2, 2, 2] - Return True
- No duplicates [1, 2, 3] - Return False
Alternative Approaches:
- Sorting: O(n log n) (time complexity), O(1) (space complexity)
- Brute Force: O(n²) (time complexity)
Interview Questions & Answers:
1. Why use a set instead of a list? Answer: Sets provide O(1) lookups while lists require O(n).
2. Can we solve in constant space? Answer: No, we need extra space for the set.
3. What if array is large? Answer: Consider memory and scalability; O(n) space may be challenging
with large inputs.
Best Approach:
Hashing (Set): O(n) time, O(n) space. Optimal solution for large input sizes.
Brute Force:
Nested Loops: O(n²) time, O(1) space. Simple but inefficient for large datasets.
Performance Considerations:
- Hashing is best for time efficiency.
- Sorting can reduce space to O(1) but at the cost of time.
- Brute Force should be avoided for large arrays due to O(n²) complexity.
Flashcards:
- Q: Why is Hashing used here? A: Hashing allows for O(1) average-time lookups to check
duplicates.
- Q: Can we use brute force here? A: Yes, but it is inefficient for large arrays due to O(n²) time
complexity.
Pattern / Trick:
Hashing is the key trick: Use a set to track seen elements and check for duplicates in constant time
(O(1)) for each element. If a duplicate is found, return True immediately. If not, continue until the end
and return False.
Code Snippets (with Comments)
Brute Force:
```python
# Brute force solution for finding duplicates
def containsDuplicateBruteForce(nums):
# Iterate over all pairs of elements
for i in range(len(nums)):
for j in range(i + 1, len(nums)): # Compare each element with the others
if nums[i] == nums[j]: # If a match is found, return True
return True
# If no duplicates are found, return False
return False
```
Optimal Solution (Using Set):
```python
# Optimal solution using hashing to find duplicates
def containsDuplicate(nums):
# Initialize an empty set to track elements we've seen
seen = set()
# Iterate through each element in the array
for num in nums:
# If the element is already in the set, it means we've found a duplicate
if num in seen:
return True # Return True immediately if a duplicate is found
# Add the current element to the set
[Link](num)
# If no duplicates are found after checking all elements, return False
return False
```
Alternative Approaches:
Sorting:
```python
# Alternative solution using sorting
def containsDuplicateSorting(nums):
# Sort the array to arrange duplicates next to each other
[Link]() # This is an in-place sort
# Check adjacent elements for duplicates
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]: # If adjacent elements are the same, return True
return True
# If no duplicates are found, return False
return False
```