Check for duplicates in an array in Java

In this post, we will see how to check for duplicates in an array in Java.

 

1. Naive Solution

Naive solution would be to check if every element in the array is repeated or not using nested for loops. The time complexity of this solution would be O(n2).

 

Download   Run Code

 

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 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).

 

Download   Run Code

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 elements of the array into a HashSet. Now the array contains a duplicate if length of the array is not equal to size of the set.

 

Download   Run Code

 

3. 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 are found to be the same, we can say that the array contains a duplicate. The time complexity of this solution is O(nlogn).

 

Download   Run Code

 

4. 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 same as the length of the array, array contains a duplicate.

 

Download   Run Code

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz