Watch 10 video solutions for Contains Duplicate, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by NeetCode has 770,501 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |