Arrays & Hashing · LC #217
Contains Duplicate
Determine whether any integer in an array appears more than once. Teaches the "seen-set" pattern for O(n) duplicate detection.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums`, return `true` if any value appears **at least twice**, and `false` if every element is distinct.
Sample I/O
Input: nums = [1, 2, 3, 1] Output: true Input: nums = [1, 2, 3, 4] Output: false
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
A set, by definition, holds only unique elements. If inserting a value fails (because it already exists), we have found a duplicate. This single invariant makes set-based detection both simple and optimal.
Core Concept
Create an empty hash set and iterate through nums. For each element, check if it is already in the set - if yes, return true. Otherwise add it and continue. If the loop finishes without a hit, return false. Equivalently in one line: compare set size to array length; any shrinkage means duplicates were present.
When to use
Detecting any duplicate in an unsorted collection in O(n) time. Building a "visited" guard during traversal. Checking set membership repeatedly.
When NOT to use
When you need the count of duplicates (use a frequency map). When the range of values is small and bounded (a boolean array beats a hash set). When the array is already sorted (compare adjacent elements in O(1) space).
Key Insights
What to Know Cold
- Hash set insertion and lookup are O(1) average, making the whole pass O(n).
- Early-return on first hit avoids scanning the rest - important for large arrays.
- Python/TS one-liner (set size vs array length) is elegant but scans the full array even if a duplicate is at index 1.
- The sorting approach (O(n log n)) uses O(1) extra space; worth mentioning as a trade-off.
- This pattern is the foundation of cycle detection in linked lists and graph visited-marking.
1 example
Worked Examples
Hash-Set Early Return
Array [1, 2, 3, 1]. Need to detect the repeated 1.
Scan left to right maintaining a seen set. At index 3, value 1 is already in the set → return true immediately without scanning the rest.
seen = set()
for n in [1, 2, 3, 1]:
if n in seen:
print(True) # True
break
seen.add(n)This is the warm-up problem most FAANG phone screens open with to verify candidates know O(n) hash-set usage before advancing to harder problems.