Contains Duplicate
Problem
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.
- 1 ≤ nums.length ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
Example
nums = [1,2,3,1]trueThe algorithm iterates through the array, maintaining a set of seen numbers. At the first element '1', the set is empty, so '1' is added. At the second element '2', '2' is not in the set, so it is added. At the third element '3', '3' is added. At the fourth element '1', the algorithm finds '1' already in the set, indicating a duplicate, and returns true immediately.
Approach
Straightforward Solution
A brute-force approach compares every element with every other element, resulting in O(n²) time complexity, which is too slow for large arrays.
Core Observation
Detecting duplicates requires checking if an element has appeared before. The fundamental operation is membership testing, which must be efficient to handle large inputs.
Path to Optimal
The key recognition signals are 'detect duplicates' and 'any value appears at least twice'. These indicate using a Hash Set because it provides O(1) average-time membership checks. By iterating once and checking if the current element is already in the set, the algorithm can detect duplicates in a single pass.
Optimal Approach
Iterate through the array once, maintaining a hash set of seen elements. For each element, check if it is in the set; if yes, return true immediately. If not, add it to the set and continue. If the loop completes without finding duplicates, return false. This guarantees O(n) time and O(n) space complexity.
Time
O(n)
Each element is processed once, and each membership check and insertion into the hash set is O(1) on average, resulting in linear time.
Space
O(n)
In the worst case, all elements are unique and stored in the hash set, requiring space proportional to the input size.
Pattern Spotlight
Hash Maps (Membership Tracking)
When the problem requires detecting duplicates or existence efficiently, use a hash-based data structure to achieve constant-time membership checks, transforming a naive O(n²) search into a linear-time solution.
Solution
| 1 | class Solution:
|
| 2 | def hasDuplicate(self, nums: List[int]) -> bool:
|
| 3 | seen = set()
|
| 4 | for num in nums:
|
| 5 | if num in seen:
|
| 6 | return True
|
| 7 | seen.add(num)
|
| 8 | return False |
Step-by-Step Solution
Maintain a Set to Track Seen Elements During Iteration
| 3 | seen = set()
|
Objective
To create a data structure that supports fast membership queries for elements encountered so far.
Key Insight
A hash set provides average O(1) time complexity for membership checks and insertions, which is essential for detecting duplicates efficiently in a single pass through the array.
Interview Quick-Check
Core Logic
Using a set to track seen elements transforms duplicate detection from O(n²) to O(n) by enabling constant-time membership checks.
Complexity
The set grows at most to the size of the input array, so space complexity is O(n).
Iterate Through the Array and Check for Duplicates
| 4 | for num in nums:
|
| 5 | if num in seen:
|
| 6 | return True
|
| 7 | seen.add(num)
|
| 8 | return False |
Objective
To scan each element and determine if it has been seen before, returning true immediately if a duplicate is found.
Key Insight
Checking for membership before insertion ensures that the algorithm detects duplicates at the earliest possible moment, allowing for early termination and improved efficiency on inputs with duplicates.
Interview Quick-Check
Core Logic
Check if the current element is already in the set before adding it; if yes, return true immediately to signal a duplicate.
Common Pitfalls & Bugs
Adding the element to the set before checking for duplicates would fail to detect duplicates correctly.
State & Boundaries
Return false after the loop if no duplicates are found, confirming all elements are unique.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if num in seen:Check if the current number is already in the set of seen elements.
This membership test is the core operation that detects duplicates immediately when they appear.
return TrueReturn true immediately upon detecting a duplicate.
Early termination upon finding a duplicate avoids unnecessary work and satisfies the problem's requirement efficiently.
seen = set()Initialize an empty set to store elements seen so far.
This set is the fundamental data structure enabling O(1) average-time membership checks, which is critical for efficient duplicate detection.
seen.add(num)Add the current number to the set of seen elements.
Adding the number after the membership check ensures that duplicates are detected correctly and that the set accurately reflects all unique elements encountered so far.
return FalseReturn false if no duplicates are found after processing all elements.
Completing the iteration without early return confirms all elements are unique, fulfilling the problem's requirement.
for num in nums:Begin iterating over each number in the input array.
Sequentially processing each element allows the algorithm to check for duplicates in a single pass.
Test Your Understanding
Why does the algorithm return immediately upon finding an element already in the set?
Because encountering an element already in the set means a duplicate exists, so the problem's condition is satisfied and no further processing is needed.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Contains Duplicate from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Start drilling Contains Duplicate for free