Contains Duplicate
Last Updated: March 29, 2026
Understanding the Problem
We need to determine whether an array contains any duplicate values. No need to find which element is duplicated or count frequencies, just a yes/no question: does any value repeat?
This is one of the most fundamental array problems, and it shows up everywhere as a building block. The key insight is that detecting duplicates boils down to efficiently checking whether we've seen a value before. The approaches differ in how they perform that "have I seen this?" check.
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, an O(n^2) brute force (checking every pair) would mean up to 10 billion comparisons. That's too slow. We need O(n log n) or better.-10^9 <= nums[i] <= 10^9→ Values span a huge range (2 billion possible values), so we can't use a simple boolean array indexed by value. We need a hash set or sorting instead.
Approach 1: Brute Force
Intuition
The most natural approach: for every element, check whether it appears anywhere else in the array. If any element matches another, we have a duplicate.
This is what you'd do mentally with a short list. Pick the first number, scan the rest. Pick the second number, scan the rest. And so on. It's correct but slow because we're doing redundant comparisons.
Algorithm
- For each element at index
i, iterate through all elements at indicesj > i. - If
nums[i] == nums[j], returntrue. - If no pair matches after checking all combinations, return
false.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n elements, we scan up to n - 1 other elements, giving roughly n * (n - 1) / 2 comparisons.
- Space Complexity: O(1). No extra data structures, only loop variables.
This works but is far too slow for large inputs. What if we sorted the array first so that duplicates would be right next to each other?
Approach 2: Sorting
Intuition
If we sort the array first, any duplicate values will end up right next to each other. So instead of checking every pair, we sort and then make a single pass looking for adjacent equal elements.
Think of it like organizing a deck of cards by number. Once they're sorted, spotting duplicates is trivial. You just scan left to right and check if any card matches the one right after it.
Algorithm
- Sort the array in ascending order.
- Iterate through the sorted array from index 0 to n - 2.
- If
nums[i] == nums[i + 1], returntrue. - If no adjacent pair matches, return
false.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n) and the subsequent linear scan is O(n), so the sort dominates.
- Space Complexity: O(1) or O(n). Depends on the sorting algorithm. In-place sorts use O(1), but many standard library sorts use O(n) internally.
Sorting works, but we don't actually need the elements in order. We only need to know if any value appears more than once. What if we used a data structure that checks membership in O(1)?
Approach 3: Hash Set
Intuition
The most efficient approach uses a hash set. As we iterate through the array, we check whether the current element already exists in the set. If it does, we've found a duplicate. If it doesn't, we add it to the set and move on.
A hash set gives us O(1) average-time lookups and insertions. So instead of the O(n) scan per element (brute force) or the O(n log n) upfront sort, we do a single O(n) pass where each element requires only O(1) work.
A hash set stores unique values and supports O(1) average-time lookups. By checking membership before inserting, we detect the first duplicate the moment it appears. The early return means we don't even process the rest of the array once a duplicate is found.
Notice how the Java and C# solutions use a neat trick: HashSet.add() returns false if the element already exists. So the membership check and insertion happen in a single call. C++ has a similar pattern with insert().second.
Algorithm
- Create an empty hash set.
- For each element in the array:
- If the element is already in the set, return
true. - Otherwise, add the element to the set.
- If the loop completes without finding a duplicate, return
false.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once. Each hash set lookup and insertion is O(1) on average.
- Space Complexity: O(n). In the worst case (all elements are distinct), the set stores all n elements.