Contains Duplicate
Understanding the Problem
We need to determine whether an array contains any duplicate values. There is no need to find which element repeats or to count frequencies. The answer is yes or no: does any value appear at least twice?
Every approach performs the same logical operation, checking whether a value has been seen before. They differ in how fast that check runs and how much memory it uses.
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 about 2 billion possibilities, so a boolean array indexed by value is impractical. A hash set or sorting handles the full range.
Approach 1: Brute Force
Intuition
Compare every element against every element after it. If any two positions hold the same value, the array contains a duplicate.
Starting the inner loop at j = i + 1 avoids comparing an element with itself and avoids checking the same pair twice. The approach is correct for any input, but the number of comparisons grows quadratically with the array length.
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.
With n up to 10^5, this exceeds typical time limits. Sorting removes most of the work: equal values end up next to each other, so only adjacent pairs need checking.
Approach 2: Sorting
Intuition
Sorting places all copies of a value in consecutive positions. After sorting, the array contains a duplicate if and only if some element equals its immediate neighbor, so a single left-to-right scan of adjacent pairs replaces the check over all pairs.
Limiting the scan to neighbors is safe because of how sorted order works: if two equal values sat at positions i and k with i < k, every element between them would be greater than or equal to nums[i] and less than or equal to nums[k], forcing it to equal both. So whenever any duplicate exists, an adjacent equal pair exists.
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(log n) to O(n), depending on the library sort. In-place quicksort variants use O(log n) stack space, while merge-sort-based implementations such as Timsort allocate up to O(n). Sorting also reorders the input array, which matters if the caller needs the original order.
Sorting spends O(n log n) establishing an ordering the scan never uses; it only needs to know whether a value has appeared before. A hash set answers that membership question in O(1) average time, trading extra memory for a faster pass.
Approach 3: Hash Set
Intuition
Iterate through the array while maintaining a hash set of values seen so far. Before processing each element, check whether it is already in the set. If it is, a duplicate exists and we return immediately, without scanning the rest of the array. If it is not, add it and continue.
A hash set supports O(1) average-time lookups and insertions. So instead of an O(n) scan per element (brute force) or an O(n log n) upfront sort, each element costs O(1) work in a single pass. This also leaves the input array untouched.
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.