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.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: You receive an integer array nums. The task is to determine whether any value appears at least twice. If a duplicate exists, return true; otherwise return false. The challenge is detecting repeated values efficiently without unnecessary comparisons.
Approach 1: HashSet Lookup (O(n) time, O(n) space)
The most practical solution uses a hash-based set to track elements you have already seen. Iterate through the array once. For each value, check whether it already exists in the set. A hash lookup is O(1) on average, so detecting a duplicate becomes an immediate constant-time check. If the value exists, return true. Otherwise insert it into the set and continue scanning the array.
The key insight is that a set guarantees uniqueness. Instead of comparing each number with every other number, the algorithm converts the duplicate detection problem into repeated hash lookups. This approach scales well for large arrays and works regardless of input ordering. Problems involving fast membership checks frequently rely on a hash table or set structure, especially when working with an array.
Approach 2: Sorting the Array (O(n log n) time, O(1) or O(log n) space)
Another option is to sort the array first, then scan for adjacent equal elements. After sorting, any duplicates must appear next to each other. Iterate from index 1 to n-1 and compare each element with the previous one. If nums[i] == nums[i-1], a duplicate exists.
The cost comes from the sorting step, which typically runs in O(n log n) time. Space usage depends on the sorting algorithm. In-place sorts like heapsort use constant space, while implementations such as Timsort may use O(log n) stack space. This method works well when the array is already being sorted for another operation or when minimizing extra memory is important. Many duplicate-detection tasks can be solved this way using techniques from sorting.
Recommended for interviews: Interviewers generally expect the HashSet solution. It demonstrates awareness of hash-based data structures and achieves optimal O(n) time. The sorting approach shows algorithmic flexibility and awareness of memory tradeoffs, but it is usually considered a secondary option since it increases time complexity. Showing both approaches signals strong problem-solving instincts: brute reasoning first, then the optimal hash-based strategy.
This approach leverages the properties of a HashSet (or similar data structures depending on the programming language), which allows for average O(1) time complexity for insertion and lookup operations. As you iterate over the array, you check if the current element is already in the HashSet. If it is, then a duplicate has been found, and you can return true immediately. If it’s not already in the HashSet, you add it. If no duplicates are found by the end of the array, you return false.
In the C solution, we sort the array using qsort() and then check each adjacent pair of elements for duplication. This is efficient given the constraints, as sorting the array is O(n log n) and the subsequent scan is O(n).
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), no extra space required apart from sorting.
This approach involves sorting the array first, then checking for duplicates by comparing each element with its next neighbor. If duplicates exist, they will appear next to each other after sorting.
Here, qsort is used to sort the array, which allows for efficient comparison of adjacent elements to find duplicates. This leverages sorting's ability to bring identical elements together.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), aside from sorting in-place.
First, we sort the array nums.
Then, we traverse the array. If there are two adjacent elements that are the same, it means that there are duplicate elements in the array, and we directly return true.
Otherwise, when the traversal ends, we return false.
The time complexity is O(n times log n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
C
We traverse the array and record the elements that have appeared in the hash table s. If an element appears for the second time, it means that there are duplicate elements in the array, and we directly return true.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Using a HashSet to Check for Duplicates | Time Complexity: O(n log n), due to the sorting step. |
| Sorting Approach | Time Complexity: O(n log n), due to sorting. |
| Sorting | — |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Lookup | O(n) | O(n) | General case; fastest solution with constant-time duplicate checks |
| Sorting + Adjacent Comparison | O(n log n) | O(1) to O(log n) | Useful when memory is limited or when the array must be sorted anyway |
Contains Duplicate - Leetcode 217 - Python • NeetCode • 1,006,464 views views
Watch 9 more video solutions →Practice Contains Duplicate with our built-in code editor and test cases.
Practice on FleetCode