Write a java program to find duplicate elements in an array. There are multiple ways through which we can find duplicate elements in an array. In this tutorial, I’ll discuss three ways to find duplicate elements in an array.
This question is also very important in terms of technical interviews.
Find Duplicate Elements in an Array – Java Program
How to Find Duplicate Elements in an Array – Java Program Examples
METHOD 1 – Using brute force approach
This is the most basic and easiest approach to search and print duplicate elements of an array. In this approach, we use two for loops (inner and outer loops) to compare an element with each element of an array. The time complexity of this approach is O(n2).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public class DuplicateElementInArray { public static void main(String[] args) { //Array declaration int arr[] = {2, 5, 3, 1, 8, 7, 5, 3}; for(int i = 0; i < arr.length; i++) { for(int j = i+1; j < arr.length; j++) { //if value is equal if(arr[i] == arr[j]) { //print the duplicate element System.out.println(arr[i]); } } } } |
This approach is not suitable for large data sets.
Find Duplicate Elements in an Array using Java HashMap
This approach is much better than the brute force approach. In this approach, we take the advantage of very important data structure called Hash Table.
Java program to find first non-repeated character in a string
Traverse an array and insert an element and it’s count (no. of occurrences). Then, Traverse a map to check all the keys whose value is greater than 1. Those keys whose value is greater than 1 are duplicate elements in an array. The Time complexity of this approach 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 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | import java.util.HashMap; import java.util.Map.Entry; import java.util.Set; public class DuplicateElementInArray { public static void main(String[] args) { int arr[] = {2, 5, 3, 1, 8, 7, 5, 3}; /** * Using Java HashMap */ HashMap<Integer, Integer> arrMap = new HashMap<>(); //Traverse an array for(int i = 0; i < arr.length; i++) { /* if element exists in a map, then increment it's count by 1, otherwise assigned a value 1 */ if(arrMap.containsKey(arr[i])) { arrMap.put(arr[i], arrMap.get(arr[i]) + 1); } else { arrMap.put(arr[i], 1); } } Set<Entry<Integer, Integer>> entry = arrMap.entrySet(); /* *Traverse the map, If any key has value greater than 1 *It means, it is duplicate element in an array */ for(Entry<Integer, Integer> ent: entry) { if(ent.getValue() > 1) { System.out.println(ent.getKey()); } } } |
Java HashSet to Find Duplicate Elements in an Array
In computer science, A set is a data structure which doesn’t allow duplicates. In java, we can use HashSet class to solve this problem. Traverse an array and insert an element into HashSet using the add() method. If the add() method returns false, it means that element is duplicate value.
The time complexity of this approach 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 | import java.util.HashSet; import java.util.Set; public class DuplicateElementInArray { public static void main(String[] args) { int arr[] = {2, 5, 3, 1, 8, 7, 5, 3}; //HashSet declaration Set arrSet = new HashSet(); //Traverse and add them for(Integer val:arr) { //If add method returns false, //it means it's a duplicate element if(arrSet.add(val) == false) { System.out.println(val); } } } } |
Conclusion
I have explained three methods to solve this problem. If you know some other approach to solve this problem, then you can let us know through your comments.
