Contains Duplicate
Problem Statement
Given an integer array nums, return true if any value appears at least twice in the array. Return false if every element is distinct.
Input
An integer array nums.
Output
A boolean: true when some value repeats, otherwise false.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^9 <= nums[i] <= 10^9
Examples
Example 1
nums = [1, 2, 3, 1]
trueExample 2
nums = [1, 2, 3, 4]
falseExample 3
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
trueLearning Objectives
- Recognise duplicate detection as a hash-set membership problem.
- Short-circuit the scan when a repeated value is found.
- Compare the hash-set solution with sorting when discussing tradeoffs.
Intuition
Pattern Recognition
The signal is a repeated membership question: have I seen this exact value before? A nested loop compares each element to all later elements, which costs O(n^2). Sorting also reveals duplicates, but it changes the ordering and costs O(n log n).
A hash set represents the values already visited. When the current value is already in the set, we have proof of a duplicate and can return immediately. If the scan finishes without a repeat, all values were distinct.
Common mistakes
- ×Counting all frequencies even though one repeat is enough to answer the question.
- ×Sorting the array without mentioning that it may mutate the input.
- ×Using a list for membership checks, which quietly returns to **O(n^2)** time.
- ×Forgetting that negative values and large values are fine because the set stores actual integers.
Algorithm Explanation
Key idea
Keep a hash set of values seen so far. Before adding a value, check whether it is already present. Presence means the current value has appeared earlier, so the array contains a duplicate.
Walkthrough
For nums = [1, 2, 3, 1], the set starts empty. Add 1, then 2, then 3. When the scan reaches the final 1, the set already contains 1, so return true without scanning anything else.
Algorithm
- Create an empty hash set seen.
- For each value in nums, check whether seen already contains it.
- If yes, return true immediately.
- Otherwise add the value to seen.
- If the loop ends, return false because no value repeated.
Solutions
Solution: Hash set membership scan
The set stores exactly the distinct values encountered so far. A duplicate is detected the first time insertion would add a value that is already present.
Step-by-step
- Allocate a HashSet<Integer> named seen.
- Scan the array from left to right.
- If the current value is in seen, return true.
- Otherwise add it to seen and continue.
- Return false after the scan when every membership check was new.
O(n)
O(n)
Expected linear time with a set that may store every distinct value.
Java implementation
Dry Run
Sample input
nums = [1, 2, 3, 1]. Track each membership check and the set after new insertions.
| step | value | seen before | membership result | seen after | answer |
|---|---|---|---|---|---|
| 1 | 1 | empty | missing | {1} | not decided |
| 2 | 2 | {1} | missing | {1, 2} | not decided |
| 3 | 3 | {1, 2} | missing | {1, 2, 3} | not decided |
| 4 | 1 | {1, 2, 3} | present | unchanged | true |
The first repeated membership check proves the answer, so there is no need to count the rest of the array.
Interview Tips
Explain the early exit. The moment a set membership check succeeds, you have found two indices with the same value. If the interviewer asks about lower space, mention sorting as a valid tradeoff only when mutating or copying the array is acceptable.
Likely follow-ups
- How would you solve it in **O(1)** extra space if you are allowed to sort the array?
- How would you return the duplicate value instead of a boolean?
- How would you detect whether any duplicate appears within distance **k**?
- How would you process values from a stream and stop on the first repeat?
Similar Problems
Key Takeaways
- Use a set when the question is only whether a value has appeared before.
- Membership checks turn duplicate detection into expected **O(n)** time.
- Return as soon as the duplicate is found; full frequency counts are unnecessary.