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] <= 109In #217 Contains Duplicate, the goal is to determine whether any value appears at least twice in a given array. The most efficient way to think about this problem is by tracking elements you have already seen.
A common approach uses a hash-based data structure such as a HashSet. As you iterate through the array, you insert each element into the set. If you encounter a value that already exists in the set, it means a duplicate has been found. This approach works because set lookups are typically O(1), making the entire scan very efficient.
Another possible strategy is to sort the array first. Once sorted, any duplicate values will appear next to each other, allowing you to detect duplicates by comparing adjacent elements. While this approach is simple, it requires additional sorting time.
Choosing between these approaches depends on constraints like memory usage and whether modifying the array is acceptable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set (Tracking Seen Elements) | O(n) | O(n) |
| Sorting + Adjacent Comparison | O(n log n) | O(1) to O(log n) depending on sorting method |
NeetCode
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.
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), no extra space required apart from sorting.
1#include <vector>
2#include <unordered_set>
3bool containsDuplicate(std::vector<int>& nums) {
4 std::unordered_set<int> seen;
5 for (int num : nums) {
6 if (seen.find(num) != seen.end()) {
7 return true;
8 }
9 seen.insert(num);
10 }
11 return false;
12}In the C++ solution, we make use of an unordered_set for efficient lookup. We iterate over the vector, check if the current number is in the set, and if not, insert it into the set. This allows for average O(1) performance for each operation.
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.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), aside from sorting in-place.
1using System;
2public class Solution {
public bool ContainsDuplicate(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Contains Duplicate or similar variations frequently appear in coding interviews at companies like Amazon, Google, and Meta. The question tests basic understanding of hashing, arrays, and time–space trade-offs.
The optimal approach uses a hash set to track elements while iterating through the array. If an element already exists in the set, a duplicate is found immediately. This method runs in O(n) time with O(n) additional space.
Yes, you can sort the array first and then compare adjacent elements to detect duplicates. This avoids additional data structures but increases the time complexity to O(n log n) due to sorting.
A hash set is the most effective data structure because it provides average O(1) insertion and lookup time. This allows you to quickly check whether an element has already appeared in the array.
C# uses Array.Sort to order the elements, which then can be checked in a single iteration for adjoining duplicates.