Java Program to Remove Duplicate Elements From the Array
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. For simplicity, we can think of an array as a fleet of stairs where on each step is placed a value
Given an array, the task is to remove the duplicate elements from the array.
Examples:
Input : a[] = {1, 1, 2, 2, 2} Output : a[] = {1,2} new size = 2 Input : a[] = {5,2,6,8,6,7,5,2,8} Output : a[] = {2,5,6,7,8} new size = 5
The ways for removing duplicate elements from the array:
Method 1: (Using extra space)
- Create a temporary array temp[] to store unique elements.
- Traverse input array and copy all the unique elements of a[] to temp[]. Also, keep count of unique elements. Let this count be j.
- Copy j elements from temp[] to a[].
Note: This approach is applicable when the array is sorted.
Implementation:
Java
// Java Program to Remove Duplicate Elements // From the Array using extra space public class Main { public static int removeduplicates( int a[], int n) { if (n == 0 || n == 1 ) { return n; } // creating another array for only storing // the unique elements int [] temp = new int [n]; int j = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { if (a[i] != a[i + 1 ]) { temp[j++] = a[i]; } } temp[j++] = a[n - 1 ]; // Changing the original array for ( int i = 0 ; i < j; i++) { a[i] = temp[i]; } return j; } public static void main(String[] args) { int a[] = { 1 , 1 , 2 , 2 , 2 }; int n = a.length; n = removeduplicates(a, n); // Printing The array elements for ( int i = 0 ; i < n; i++) System.out.print(a[i] + " " ); } } |
1 2
Complexity Analysis
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Method 2: (Constant extra space)
Implementation: Just maintain a separate index for the same array as maintained for different array in Method 1.
Java
// Java Program to Remove Duplicate Elements // From the Array using extra space public class Main { public static int removeDuplicates( int a[], int n) { // if(array size if 0 or 1 array is already sorted) if (n == 0 || n == 1 ) { return n; } int j = 0 ; // check if the ith element is not equal to // the (i+1)th element, then add that element // at the jth index in the same array // which indicates that te particular element // will only be added once in the array for ( int i = 0 ; i < n - 1 ; i++) { if (a[i] != a[i + 1 ]) { a[j++] = a[i]; } } a[j++] = a[n - 1 ]; return j; } public static void main(String[] args) { int a[] = { 1 , 2 , 2 , 3 , 3 , 4 , 4 , 4 , 5 , 5 , 6 }; int n = a.length; int j= 0 ; // the function will modify the array a[] // such that the starting j elements // will be having all unique elements // and no element will be appearing more than // once j = removeDuplicates(a, n); // printing array elements for ( int i = 0 ; i < j; i++) System.out.print(a[i] + " " ); } } |
1 2 3 4 5 6
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)
Note: Both the methods mentioned above can be used if the array is sorted. So for using above-mentioned method is array is not sorted you need to sort the array. You can use the in-built method Arrays.sort() to sort the array. If sorting of the array is done using this method then the Time complexity of the program increases from O(n) to O(nlogn).
Method 3: Using Set
This method can be used even if the array is not sorted.
Approach:
- Take a Set
- Insert all array elements in the Set. Set does not allow duplicates and sets like LinkedHashSet maintains the order of insertion so it will remove duplicates and elements will be printed in the same order in which it is inserted.
- Print elements of Set.
Implementation:
Java
// Java Program to Remove Duplicate Elements // From the Array using Set import java.util.*; class GFG { // Function to remove duplicate from array public static void removeDuplicates( int [] a) { LinkedHashSet<Integer> set = new LinkedHashSet<Integer>(); // adding elements to LinkedHashSet for ( int i = 0 ; i < a.length; i++) set.add(a[i]); // Print the elements of LinkedHashSet System.out.print(set); } // Driver code public static void main(String[] args) { int a[] = { 5 , 2 , 6 , 8 , 6 , 7 , 5 , 2 , 8 }; // Function call removeDuplicates(a); } } |
[5, 2, 6, 8, 7]
Time complexity: O(n), where n is the number of elements in the input array.
Space complexity: O(n), where n is the number of elements in the input array. This is because the LinkedHashSet will store all unique elements of the input array, and the number of unique elements in the worst case could be equal to the number of elements in the input array.
Method 4: Using Frequency array
We can use the frequency array if the range of the number in the array is limited, or we can also use a set or map interface to remove duplicates if the range of numbers in the array is too large.
Approach:
- Find the Maximum element (m) in the array.
- Create a new array of size m+1.
- Now traverse the input array and count the frequency of every element in the input array.
- Now traverse the frequency array and check for the frequency of every number if the frequency of the particular element is greater than 0 then print the number.
Implementation:
Java
// Java Program to Remove Duplicate Elements // From the Array by maintaining frequency array import java.util.*; class GFG { public static void main(String[] args) { int a[] = { 5 , 2 , 6 , 8 , 6 , 7 , 5 , 2 , 8 }; int n = a.length; // m will have the maximum element in the array. int m = 0 ; for ( int i = 0 ; i < n; i++) { m = Math.max(m, a[i]); } // creating the frequency array int [] f = new int [m + 1 ]; // incrementing the value at a[i]th index // in the frequency array for ( int i = 0 ; i < n; i++) { f[a[i]]++; } for ( int i = 0 ; i < m + 1 ; i++) { // if the frequency of the particular element // is greater than 0, then print it once if (f[i] > 0 ) { System.out.print(i + " " ); } } } } |
2 5 6 7 8
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(m)
Method 5: Using HashMap
The above frequency method will not be useful if the number is greater than 106 or if the array is of strings. In this case, we have to use HashMap.
Approach:
- Create a HashMap to store the unique elements.
- Traverse the array.
- Check if the element is present in the HashMap.
- If yes, continue traversing the array.
- Else Print the element and store the element in HashMap.
Implementation:
Java
// Java Program to Remove Duplicate Elements // From the Array using HashMap import java.util.HashMap; class GFG { static void removeDups( int [] a, int n) { // Hash map which will store the // elements which has appeared previously. HashMap<Integer, Boolean> mp = new HashMap<>(); for ( int i = 0 ; i < n; ++i) { // Print the element if it is not // present there in the hash map // and Insert the element in the hash map if (mp.get(a[i]) == null ) { System.out.print(a[i] + " " ); mp.put(a[i], true ); } } } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 5 , 1 , 7 , 2 , 4 , 2 }; int n = arr.length; removeDups(arr, n); } } |
1 2 5 7 4
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(m)
Contact Us