875858. Check if array contains duplicates
Easy
Check if array contains duplicates
Slug: check-if-array-contains-duplicates
Difficulty: Easy
Id: 875858
Topic Tags: Arrays, Hash
Company Tags: None
Summary
Given an integer array, write a function that checks if the array contains duplicate elements. This problem involves arrays and hash tables as key concepts.
Detailed Explanation
To solve this problem, we can use a hash set to keep track of unique elements in the array. We iterate through each element in the array and check if it is present in the hash set. If an element is found in the hash set, it means that the array contains duplicates for that element.
Here's a step-by-step breakdown of the solution:
- Initialize an empty hash set.
- Iterate through each element in the array.
- For each element, check if it is present in the hash set.
- If the element is not found in the hash set, add it to the set and mark it as unique.
- If the element is already present in the hash set, return true indicating that the array contains duplicates.
Here's a time complexity analysis of the solution:
- Time complexity: O(n) where n is the size of the array.
- Space complexity: O(min(n, m)) where m is the size of the hash set. In the worst-case scenario, the size of the hash set can be equal to the size of the array.
Optimized Solutions
Java
import java.util.HashSet;
public class Main {
public static boolean hasDuplicates(int[] arr) {
HashSet<Integer> set = new HashSet<>();
for (int i : arr) {
if (!set.add(i)) {
return true;
}
}
return false;
}
}