Write a java program to find duplicate elements in an array. Given an array of integers, We have to write a code to find all duplicate elements in an array.
For example :
Input : arr = { 2, 5, 3, 1, 8, 7, 5, 3, 2 }
Output: {5, 3, 2}
In this tutorial, I am going to explain three approaches to find duplicate elements in an array. This question is also very important for technical interviews.
Find Duplicate Elements in an Array – Java Program
How to Find Duplicate Elements in an Array
METHOD 1 – Using brute force approach
This is the most basic and easiest approach to find 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 19 | //Brute force approach to print duplicate elements of an array 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 HashMap
This approach is much better than the brute force approach.
Java program to find first non-repeated character in a string
In this approach, we traverse an array and create a map of array element and it’s count. 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 */ Map<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()); } } } |
Find Duplicate Elements in an Array using Set
The set data structure doesn’t allow duplicates. In java, we take the advantage of set to identify duplicate elements of an array.
Traverse an array and insert an element into Set using the add() method. If the add() method returns false, it means that element is already present in set.
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 | 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}; Set arrSet = new HashSet<>(); for (int i = 0; i < arr.length; i++) { if (arrSet.contains(arr[i])) { System.out.println(arr[i]); } else { arrSet.add(arr[i]); } } } } |
In these video tutorials, I have explained how we can find all duplicates in an array.
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.
