If you have to write a Java program to find duplicate elements in an array one option you have is to loop through the array taking one element at a time and then compare it with all the other elements of the array in order to find the duplicates. Though this solution works fine but the problem here is you are looping though the array twice making the time complexity of this solution O(n2). Because of the double iteration program will be slow.
Another option to find duplicate elements in an array is to sort the array first and then compare the adjacent element in a loop. Since array is sorted so the repeated elements would be adjacent to each other so you don't need an inner loop to compare current element with all the elements of the array. Thus the time complexity of this solution is O(nlogn + n). Time required for sorting is O(nlogn) and iteration of the array requires O(n) time.
To further minimize the execution time you can think of using a data structure like HashSet which will reduce the time complexity to O(n).
Since Set doesn't allow duplicate elements trying to do that will return false. So you can have a logic where you iterate an array and try to add element to the HashSet, if adding an element to the HashSet returns false that means a duplicate element. As I said since array is iterated only once so time complexity is O(N) here but a new data structure is created, apart from array you are also creating a Set, so space complexity increases here, extra space used is O(N).
Let's see Java program to find duplicate elements in an array using all of the approaches discussed above.
Looping through unsorted Array and comparing elements to find duplicates
Here you have an outer loop that iterates the array one element at a time and another loop that starts from the next element and iterates through all the elements of the array and compares it with the current element.
public class DuplicateArrayElement {
public static void main(String[] args) {
int[] numArray = {2, 6, 7, 6, 2, 19, 1, 19};
for(int i = 0; i < numArray.length; i++){
for(int j = i + 1; j < numArray.length; j++){
if(numArray[i] == numArray[j]){
System.out.println("Duplicate element found " + numArray[j]);
}
}
}
}
}
Output
Duplicate element found 2 Duplicate element found 6 Duplicate element found 19
Finding duplicate elements in a sorted Array
public class DuplicateArrayElement {
public static void main(String[] args) {
int[] numArray = {8, 1, 7, 6, 2, 19, 1, 19};
// sort array
Arrays.sort(numArray);
for(int i = 0; i < numArray.length - 1; i++){
if(numArray[i] == numArray[i+1]){
System.out.println("Duplicate element found " + numArray[i]);
}
}
}
}
Output
Duplicate element found 1 Duplicate element found 19
Using HashSet to find duplicate elements in an array
In this solution to find duplicate elements in an array in Java, iteration of the array is done and elements of the array are added to the set.
Here thing to understand is- If set already contains the element, call to add method of the set leaves the set unchanged and returns false. So, whenever false is returned that means a duplicate element.
public class DuplicateArrayElement {
public static void main(String[] args) {
int[] numArray = {2, 6, 7, 6, 2, 19, 1, 19};
Set<Integer> numSet = new HashSet<Integer>();
for(int num : numArray){
// If add returns false
if(!numSet.add(num)){
System.out.println("Duplicate element found " + num);
}
}
}
}
Output
Duplicate element found 2 Duplicate element found 6 Duplicate element found 19
That's all for this topic Find Duplicate Elements in an Array Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-