Write a Java program to remove duplicate elements from an array is a frequently asked interview question and you may be asked to do it without using any of the collection data structure like List or Set or you may be asked to do it using Collection API classes first and then without using any of those classes.
In this post we’ll see Java programs for removal of duplicate elements in an array using Collection API classes, without Collection API and using Java Stream API.
Using Collection API
One way to remove duplicate elements from an array in Java is to copy your array elements to a HashSet. As you know HashSet only stores unique elements so any repetition of an element will be discarded. Using this property of HashSet once you copy all the array elements to a HashSet you’ll have a Set with only unique elements. Now you can again copy the elements from your Set to create an array which will be your array with duplicate elements removed.
Remove Duplicate Elements From an Array using HashSet
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DuplicateRemoval {
public static void main(String[] args) {
int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
int[] outArr = removeDuplicatesUsingSet(intArr);
System.out.println("Original array");
for(int i : intArr){
System.out.print(i+" ");
}
System.out.println("");
System.out.println("after removal");
for(int i : outArr){
System.out.print(i+" ");
}
}
/**
* @param input
* @return
*/
public static int[] removeDuplicatesUsingSet(int[] input){
// Adding array elements to a list
List<Integer> tempList = new ArrayList<Integer>();
for(int i : input){
tempList.add(i);
}
// creating a set using list
Set<Integer> set = new HashSet<Integer>(tempList);
Integer[] output = new Integer[set.size()];
int[] arrOut = new int[output.length];
set.toArray(output);
int j =0;
for(Integer i : output){
arrOut[j++] = i;
}
return arrOut;
}
}
Output
Original array 1 2 2 5 1 6 12 7 12 12 3 8 after removal 1 2 3 5 6 7 8 12
Few things to note here are-
- If you are using Set then ordering with in the array doesn’t matter i.e. Array doesn’t have to be sorted.
- Ordering of the original array will not be retained once elements are stored in the Set.
- In the above code I have used int[] array (array of primitives) that’s why there are some extra steps like creating Array of Integer[] (Integer objects) as toArray() method of the Set works only with objects. If you have an array of objects then you don’t need these extra steps.
Remove Duplicate Elements From an Array using LinkedHashSet
In the above Java code to delete element from an array using HashSet, ordering of the array elements is not retained, if you want ordering to be retained then use LinkedHashSet instead.
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
public class DuplicateRemoval {
public static void main(String[] args) {
int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
int[] outArr = removeDuplicatesUsingSet(intArr);
System.out.println("Original array");
for(int i : intArr){
System.out.print(i+" ");
}
System.out.println("");
System.out.println("after removal");
for(int i : outArr){
System.out.print(i+" ");
}
}
/**
* @param input
* @return
*/
public static int[] removeDuplicatesUsingSet(int[] input){
// Adding array elements to a list
List<Integer> tempList = new ArrayList<Integer>();
for(int i : input){
tempList.add(i);
}
// creating a set using list
Set<Integer> set = new LinkedHashSet<Integer>(tempList);
Integer[] output = new Integer[set.size()];
int[] arrOut = new int[output.length];
set.toArray(output);
int j =0;
for(Integer i : output){
arrOut[j++] = i;
}
return arrOut;
}
}
Output
Original array 1 2 2 5 1 6 12 7 12 12 3 8 after removal 1 2 5 6 12 7 3 8
Now you can see ordering of the array elements is retained. For duplicate elements first occurrence of the element is retained.
Java Example without using Collection
If you have to remove duplicate elements of the array without using any of the Collection API classes then you can use the following code.
In the program input array is sorted first so that all the duplicate elements are adjacent to each other. By doing that you need only a single loop for comparison.
For removing duplicate elements you need to shift all the elements after the duplicate to the left. Another thing to note here is that array size is fixed once defined, when duplicate element is removed and you shift element after the duplicate to the left that creates space on the right side of the array. To remove that space you need to truncate the array by using copyOf() method of the Arrays utility class.
public class DuplicateRemoval1 {
/**
* @param input
* @return
*/
public static int[] removeDuplicates(int[] intArr){
int i = 1;
int j = 0;
Arrays.sort(intArr);
System.out.println("Sorted array");
for(int x : intArr){
System.out.print(x+" ");
}
while(i < intArr.length){
if(intArr[i] == intArr[j]){
i++;
}else{
intArr[++j] = intArr[i++];
}
}
// This is required to truncate the size of the array
// otherwise array will retain its original size
int[] output = Arrays.copyOf(intArr, j+1);
return output;
}
public static void main(String[] args) {
int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
int[] outArr = removeDuplicates(intArr);
System.out.println("");
System.out.println("after removal");
for(int i : outArr){
System.out.print(i+" ");
}
}
}
Output
Sorted array 1 1 2 2 3 5 6 7 8 12 12 12 after removal 1 2 3 5 6 7 8 12
Time and space complexity
As per the description of the Arrays.sort() method its time complexity is O(n*logn). Then array is traversed in the while loop which takes O(n) time thus the time complexity of the above code is O(n*logn+n).
Using Java Stream to remove duplicates from array
Java Stream API (From Java 8) also provides an option to remove duplicate elements from an array. You can use distinct() method in Java Stream to remove duplicate elements.
int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
int tempArr[] = Arrays.stream(intArr).distinct().toArray();
System.out.println("");
System.out.println("after removal");
for(int i : tempArr){
System.out.print(i+" ");
}
Output
after removal 1 2 5 6 12 7 3 8
That's all for this topic Remove Duplicate Elements From an Array in Java. 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-