Check for duplicates in an array in Java
This post will discuss how to check for duplicates in an array in Java.
1. Naive Solution
A naive solution is to check if every array element is repeated or not using nested for-loops. The time complexity of this solution would be O(n2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Generic method to check for duplicates in an array private static <T> boolean checkForDuplicates(T... array) { // for every array element, check if it is found afterward in the array for (int i = 0; i < array.length; i++) { for (int j = i + 1; j < array.length; j++) { if (array[i] != null && array[i].equals(array[j])) { return true; } } } // no duplicate is found return false; } |
2. Using HashSet
We can perform better by using Hashing. The idea is to traverse the given array and insert each encountered element into a HashSet. Now, if the encountered element was already present in the set, it is a duplicate. The time complexity of this solution is O(n) but auxiliary space used is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Generic method to check for duplicates in an array private static <T> boolean checkForDuplicates(T... array) { // create an empty set Set<T> set = new HashSet<T>(); // do for every array element for (T e: array) { // return true if a duplicate is found if (set.contains(e)) { return true; } // insert the current element into a set if (e != null) { set.add(e); } } // no duplicate is found return false; } |
We know that HashSet doesn’t allow duplicate values in it. We can make use of this property to check for duplicates in an array. The idea is to insert all array elements into a HashSet. Now the array contains a duplicate if the array’s length is not equal to the set’s size.
|
1 2 3 4 5 6 7 |
// Generic method to check for duplicates in an array private static <T> boolean checkForDuplicates(T... array) { Set<T> set = new HashSet<>(Arrays.asList(array)); return array.length != set.size(); } |
3. Using Sorting
The idea is to sort the array in natural or reverse order. Now we traverse the array and compare adjacent elements. If any adjacent element is found to be the same, we can say that the array contains a duplicate. The time complexity of this solution is O(n.log(n)).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Generic method to check for duplicates in an array private static <T> boolean checkForDuplicates(T... array) { // sort the array in natural or reverse order Arrays.sort(array); // prev stores the previous element for the current element in the array T prev = null; // do for every array element for (T e: array) { // if two consecutive elements are found to be equal, // a duplicate is found if (e != null && e.equals(prev)) { return true; } // set the current element as previous prev = e; } // no duplicate is found return false; } |
4. Using Java 8
In Java 8, we can make use of streams to count distinct elements present in the array. If the distinct count is not the same as the array’s length, the array contains a duplicate.
|
1 2 3 4 5 6 |
// Generic method to check for duplicates in an array private static <T> boolean checkForDuplicates(T... array) { Long distinctCount = Stream.of(array).distinct().count(); return array.length != distinctCount; } |
That’s all about checking for duplicates in an array in Java.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)