In this blog, we will explore various methods to achieve this using Java programming. By the end of this journey, you will have a clear understanding of different approaches to remove duplicates, along with their advantages and disadvantages.
In the world of programming, managing and processing data efficiently is paramount. Duplicate elements in an array can lead to inefficiencies in data manipulation and can also skew the accuracy of results. Therefore, it becomes essential to have techniques to remove duplicate elements from an array.
Method 1: Using extra space
Below given Java Program is to remove duplicate elements in an Array Using the extra space method:
// Java Program to Remove Duplicate Elements in an Array
public class Main {
public static int removeduplicate(int arr[], int n)
{
if (n == 0 || n == 1) {
return n;
}
int[] temp = new int[n];
int j = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] != arr[i + 1]) {
temp[j++] = arr[i];
}
}
temp[j++] = arr[n - 1];
// Changing the original array
for (int i = 0; i < j; i++) {
arr[i] = temp[i];
}
return j;
}
public static void main(String[] args)
{
int arr[] = { 11, 11, 32, 2, 2 };
System.out.print("Elements of given array are: ");
for (int k = 0; k < arr.length; k++) {
System.out.print(arr[k] + " ");
}
int n = arr.length;
n = removeduplicate(arr, n);
System.out.print("\nElements of new array are: ");
// Printing The array elements
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Approach:
The given Java program aims to remove duplicate elements from an array while maintaining the order of the unique elements. The approach uses an auxiliary array `temp` to store the unique elements, and then copies them back to the original array `arr`. The idea is to iterate through the input array and compare each element with its adjacent element. If they are different, the element is considered unique and is added to the `temp` array.
Code Explanation:
1. First, the `removeduplicate` method takes an array `arr` and its length `n` as parameters.
2. A temporary array `temp` of the same length as the input array is created to store the unique elements.
3. A variable `j` is initialized to 0 to keep track of the current index in the `temp` array.
4. A loop iterates through the input array `arr`. If the current element is not equal to the next element, it is considered unique and is added to the `temp` array.
5. After processing all elements, we add the last element of the input array to the ‘temp’ array, as it is always unique.
6. Another loop is used to copy the elements from the `temp` array back to the original array `arr`.
7. The method returns the new length of the modified array.
8. The ‘main’ method declares and initializes an array ‘arr’ with duplicate elements.
9. Next, the original array elements are printed.
10. The `removeduplicate` method is called to modify the array and obtain the new length.
11. Finally, the modified array elements are printed.
Check out Javascript for Loop, Now!
Output:
Elements of given array are: 11 11 32 2 2
Elements of new array are: 11 32 2 Time Complexity:
The time complexity of the given approach is O(n), where n is the number of elements in the array. This occurs because we process each element once to eliminate duplicates, and the copying of elements back to the original array also consumes O(n) time.
Space Complexity:
The space complexity of the approach is O(n) as well, since an additional array `temp` of the same size as the input array is used to store unique elements.
Method 2: Using Constant extra space
Check out the given Java Program to remove duplicate elements in an Array Using Constant extra space method:
Understand the Concept of Xylem and Phloem Number in Java, here!
// Java Program to Remove Duplicate Elements in an Array
public class Main {
public static int removeDuplicates(int a[], int num)
{
// if(array size if 0 or 1 array is already sorted)
if (num == 0 || num == 1) {
return num;
}
int j = 0;
for (int i = 0; i < num - 1; i++) {
if (a[i] != a[i + 1]) {
a[j++] = a[i];
}
}
a[j++] = a[num - 1];
return j;
}
public static void main(String[] args)
{
int a[] = { 11, 42, 52, 23, 23, 74, 74, 64, 85, 85, 4 };
int num = a.length;
int j=0;
j = removeDuplicates(a, num);
// printing array elements
for (int i = 0; i < j; i++)
System.out.print(a[i] + " ");
}
}
Approach:
The given program aims to remove duplicate elements from an array while maintaining the order of the remaining unique elements. It uses a two-pointer approach to achieve this. The `removeDuplicates` method takes an array `a[]` and the number of elements `num` as parameters. It iterates through the array and checks for duplicate elements. When you find a unique element, place it at the position indicated by the variable j. After iterating through the array, the unique elements are positioned at the beginning of the array, and the value of `j` represents the length of the modified array with duplicates removed.
Code Explanation:
1. The `removeDuplicates` method first checks if the array size is 0 or 1. If so, it returns the length of the array as there are no duplicates to remove.
2. A variable `j` is used to keep track of the position for placing unique elements.
3. The loop iterates through the array from index 0 to `num – 2`. It compares each element with its adjacent element.
4. If the current element `a[i]` is not equal to the next element `a[i + 1]`, it means the element is unique, so it is placed at the position indicated by `j`, and `j` is incremented.
5. After the loop, the last element of the original array is also added to the modified array to account for the last unique element.
6. The method returns the value of `j`, representing the length of the modified array.
7. In the `main` method, an example array `a` is defined.
8. The length of the array is stored in the variable `num`.
9. The `removeDuplicates` method is called, and its result is stored in the variable `j`.
10. Finally, a loop prints the unique elements of the modified array up to index `j`.
Output:
11 42 52 23 74 64 85 4Time Complexity:
The time complexity of this approach is O(n), where n is the number of elements in the array. The loop iterates through the array once to identify and place unique elements.
Space Complexity:
The space complexity of this approach is O(1), as it uses a constant amount of extra space for variables `j` and loop variables, regardless of the size of the input array.
Method 3: Using Set
Below given Java Program to remove duplicate elements in an Array Using the Set method:
// Java Program to Remove Duplicate Elements in an Array
import java.util.*;
class RemoveElementEx {
// Function to remove duplicate from array
public static void removeDuplicates(int[] arr)
{
LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
System.out.print("Elements of new array are: ");
// adding elements to LinkedHashSet
for (int i = 0; i < arr.length; i++)
set.add(arr[i]);
// Print the elements of LinkedHashSet
System.out.print(set);
}
// Driver code
public static void main(String[] args)
{
int arr[] = {5,12,8,86,6,7,5,12,8};
System.out.print("\n Elements of given array are: ");
for (int i = 0; i < arr.length; i++) {
// Print array element present at index i
System.out.print(arr[i] + " ");
}
// Function call
removeDuplicates(arr);
}
}
Approach:
The Java program aims to remove duplicate elements from an array using the LinkedHashSet data structure. LinkedHashSet is used because it maintains the order of elements and automatically removes duplicates as they are added.
Code Explanation:
1. Import the `java.util` package which includes classes for data manipulation.
2. Next, define a class `RemoveElementEx`.
3. Inside the class, define a static method `removeDuplicates` that takes an integer array as input and removes duplicates using a LinkedHashSet.
4. Next, create a LinkedHashSet named `set` to store unique elements.
5. Iterate through the input array and add each element to the LinkedHashSet.
6. Print the elements of the LinkedHashSet, which will automatically remove duplicates.
7. In the `main` method, create an integer array `arr` with duplicate elements.
8. Print the original array.
9. Finally, call the ‘removeDuplicates’ method to eliminate duplicates, and then print the new array without any repeated elements.
Output:
Elements of given array are: 5 12 8 86 6 7 5 12 8
Elements of new array are: [5, 12, 8, 86, 6, 7]Time Complexity:
The time complexity of this approach depends on the size of the input array. Adding elements to the LinkedHashSet takes O(n) time, where n is the number of elements in the array. Printing the elements of the LinkedHashSet also takes O(n) time. Therefore, the overall time complexity is O(n).
Space Complexity:
The LinkedHashSet’s space usage determines the space complexity for storing unique elements. In the worst case, if all elements are unique, the LinkedHashSet will use O(n) space. Hence, the space complexity of this approach is O(n).
Get a Complete list of Online Certification Courses in India here!
Method 4: Using Frequency Array
Check out the below Java Program to remove duplicate elements in an Array Using Frequency Array method:
// Java Program to Remove Duplicate Elements in an Array
import java.util.*;
class RemoveElementEx {
public static void main(String[] args)
{
int a[] = { 15, 42, 36, 8, 36, 7, 15, 42, 8 };
System.out.print("Elements of given array are: ");
for (int i = 0; i < a.length; i++) {
// Print array element present at index i
System.out.print(a[i] + " ");
}
int num = a.length;
// m will have the maximum element in the array.
int m = 0;
for (int i = 0; i < num; i++) {
m = Math.max(m, a[i]);
}
// creating the frequency array
int[] f = new int[m + 1];
for (int i = 0; i < num; i++)
{
f[a[i]]++;
}
System.out.print("\nElements of given array are: ");
for (int i = 0; i < m + 1; i++)
{
if (f[i] > 0) {
System.out.print(i + " ");
}
}
}
}
Approach:
The given Java program aims to remove duplicate elements from an array using a frequency-based approach. Additionally, The process involves creating a frequency array to track the count of occurrences of each element in the original array. Once the frequency array is populated, the unique elements are printed based on their counts.
Code Explanation:
1. Initialize the original array `a` containing the elements with duplicates.
2. Next, find the length of the array `num`.
3. Identify the maximum element `m` present in the array.
4. Create a frequency array `f` of size `(m + 1)` to store the count of occurrences of each element.
5. To begin, iterate through the original array ‘a’, subsequently populating the frequency array ‘f’ according to the values of the elements.
6. Print the unique elements by iterating through the frequency array and printing the indexes where the count is greater than 0.
Output:
Elements of given array are: 15 42 36 8 36 7 15 42 8
Elements of given array are: 7 8 15 36 42 Time Complexity
You can analyze the time complexity of this approach as follows:
– Iterating through the original array to find the maximum element: O(n)
– Creating and populating the frequency array: O(n)
– Finally, iterating through the frequency array to print unique elements: O(m), where m is the maximum element in the array
Overall time complexity: O(n + m)
Space Complexity
-Original array space requirement: O(n)
-Frequency array space requirement: O(m)
– Additional space for variables and iterators: O(1)
Overall space complexity: O(n + m + 1), where n is the length of the original array and m is the maximum element in the array.
Method 5: Using HashMap
Below given Java Program to remove duplicate elements in an Array Using HashMap method:
// Java Program to Remove Duplicate Elements in an Array
import java.util.HashMap;
class RemoveElementEx {
static void removeDups(int[] a, int n)
{
HashMap<Integer, Boolean> mp = new HashMap<>();
for (int i = 0; i < n; ++i) {
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 = { 41, 20, 5, 41, 7, 20, 44, 20 };
System.out.print("Elements of given array are: ");
for (int i = 0; i < arr.length; i++) {
// Print array element present at index i
System.out.print(arr[i] + " ");
}
int n = arr.length;
System.out.print("\nElements of given array are: ");
removeDups(arr, n);
}
}
Approach:
The program uses a HashMap to efficiently remove duplicate elements from an array. To achieve this, the fundamental idea is to iterate through the array and subsequently store each unique element in the HashMap. If an element is already present in the HashMap, it is considered a duplicate and is not printed. Therefore, only unique elements are printed to the console.
Code Explanation:
1. To begin, import the ‘java.util.HashMap’ class.
2. Next, define a class named ‘RemoveElementEx’.
3. Afterward, declare a static method ‘removeDups’ that takes an array a and an integer n as parameters.
4. Moving on to the inside of the method:
– Create a `HashMap` named `mp` to store unique elements.
– Iterate through the array `a` using a `for` loop:
– If the current element `a[i]` is not present in the `HashMap` (`mp.get(a[i])` returns `null`), then:
– Print the element.
– Put the element in the `HashMap` with a value of `true`.
5. In the `main` method:
– Declare an array `arr` with some duplicate elements.
– Print the original array elements using a loop.
– Next, calculate the length of the array and store it in variable `n`.
– Print a message indicating that duplicates are being removed.
– Finally, call the `removeDups` method to remove duplicates and print the unique elements.
Output:
Elements of given array are: 41 20 5 41 7 20 44 20
Elements of given array are: 41 20 5 7 44 Time Complexity:
– The `removeDups` method iterates through the array once, resulting in a time complexity of O(n), where n is the number of elements in the array.
Space Complexity:
– The program uses additional space to store unique elements in the `HashMap`. Therefore, the space complexity is O(k), where k is the number of unique elements in the array. In the worst case, where all elements are unique, the space complexity would be O(n).
Tips & Tricks to Remove Duplicate Elements
10 Tips and tricks to implement a Java program to remove duplicate elements in an array effectively:
1. Use a Set Data Structure: Utilize a `HashSet` or `LinkedHashSet` to store unique elements. This automatically eliminates duplicates while maintaining insertion order.
2. Sort the Array: Before removing duplicates, sort the array using `Arrays.sort()` to group identical elements. Then, iterate through the sorted array, and duplicates will be adjacent.
3. Stream API: Utilize Java’s Stream API to filter distinct elements from the array and collect them using `Collectors.toList()`.
4. Frequency Counting: Create an array to keep track of the frequency of each element. Iterate through the original array, and if the frequency is 1, add the element to a new array.
5. In-Place Removal: Instead of creating a new array, perform in-place removal of duplicate elements. Maintain a separate index for the next non-duplicate element to overwrite duplicates.
6. Use a Map: Create a `HashMap` to store elements as keys and their frequencies as values. Then, iterate through the map and add elements with frequency 1 to a new array.
7. LinkedHashSet for Order Preservation: If you need to preserve the order of elements, use a `LinkedHashSet` to eliminate duplicates while maintaining insertion order.
8. Custom Sorting: Implement a custom sorting algorithm that groups identical elements together. Then, traverse the sorted array and remove adjacent duplicates.
9. Recursion: Implement a recursive function that compares each element with the rest of the array and subsequently removes duplicates.
10. Bit Manipulation: For small integer values, use a bitset or bitwise XOR operation to identify unique elements and remove duplicates.
In conclusion, mastering techniques to remove duplicate elements from arrays is crucial for efficient programming. Different approaches, such as extra space, constant space, sets, or frequency arrays, have their advantages and disadvantages. Understanding these techniques enhances coding skills and problem-solving abilities.
We hope that our blog on ‘Java Program to Remove Duplicate Elements in an Array’ helps you to understand various methods to achieve this. You can also visit our Newtum website for more information on various courses and blogs about PHP, C Programming for kids, Java, and more. Happy coding with Newtum!
About The Author
