Java Program for Removing Duplicates Elements from an Array

Last Updated on May 18, 2023 by Prepbytes

A collection of items stored in consecutive places in memory is known as an array. The goal is to group objects of the same category for storage. For ease of understanding, consider an array as a series of stairs with a value placed on each level.

What are Duplicate Elements in an Array?

Duplicate elements are those elements that occurred in an array more then once. Let’s take a look at {1,2,3,4,2}, in this example, 2 is having a duplicate element as it is occurring more than once.

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

Methods for Eliminating Duplicate Elements from an Array

Removing duplicate elements from an array can be implemented in various ways. We will discuss 5 different ways to remove duplicate elements from an array.

• Using extra space
• Constant extra space
• Using Set
• Using Frequency Array
• Using HashMap

Method 1: Removing Duplicate Elements from an Array Using Extra Space

This is how the array duplicates are removed using brute force. This approach makes use of extra space.

Algorithm:

1. To hold unique elements, make a temporary array called temp[].
2. traverse the input array, copying to temp all of a’s distinctive elements where a is the original array. Keep track of the distinct aspects as well. Let j be the count.
3. J items are copied from temp[] to a[].

Note: When the array is sorted, this strategy is appropriate.

Code Implementation

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] + " ");
    }
}

Output

1 2

Complexity Analysis

Time Complexity: O(N) as we are running a loop from 0 to N where N is the number of elements present in the array.
Auxiliary Space: O(N) as we are taking an extra array “temp” of space N.

Method 2: Removing Duplicate Elements from an Array Using Constant Extra Space

In this method, we won’t use any extra space; instead, we’ll just change the provided array so that the first k elements are the unique ones and the rest are duplicates. Then, we’ll return the value of k. Thus, we can eliminate duplicates from an array in this way.

Algorithm:

1. Sort The Array Elements.
2. Since we know that the first element will always be unique, we keep a reference called k that counts down the unique elements starting at 1.
3. From i=0 to i=n-2, execute a loop.
4. If a[i]!=a[i+1], then change the value of a[k]=a[i] and k++
5. else continue;
6. Insert the a[n-1] element to the res array.
7. We will print the entries present in the index range from i=0 to i=k-1 before returning the value of k, which is now the total number of unique elements in the array.

Code Implementation

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
  
    public static void removeDuplicates(int a[], int n)
    {
        int j = 0;
        Arrays.sort(a);
        for (int i = 0; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                a[j++] = a[i];
            }
        }  
        a[j++] = a[n - 1];
        for (int i = 0; i < j; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void main(String[] args)
    {
        int a[] = {1,2,1,2,3,4,5,6,4,4,5,5};
        int n = a.length;
        removeDuplicates(a, n);
    }
}

Output

1 2 3 4 5 6

Complexity Analysis:

Time Complexity: O(NLogN) as we are using Arrays.sort() method in our logic.
Auxiliary Space: O(1) as we are using constant space in this approach.

Note: If the array is sorted, either of the aforementioned approaches can be utilized. Therefore, if the array is not sorted before using the method above, you must sort the array. To sort the array, use the built-in method Arrays.sort(). If the array is sorted using this method, the program’s time complexity rises from O(N) to O(NlogN).

Method 3: Removing Duplicate Elements from an Array Using Set

The Set Data structure will be used in this approach to eliminate duplicates from the array. In the end, we will change the supplied array so that the first k elements are the unique elements, and we will then return k, the total number of unique elements.

Note: A set is a type of data structure that only keeps one instance of each element that is added to it.

Algorithm:

1. Make a set named s.
2. Add all of the array’s components to the set.
3. Maintain a pointer called k and set its initial value to 0.
4. As you begin to iterate through the set, change the array as a[k]=x and k++, where x represents an element in the set.
5. We will print the entries present in the index range from i=0 to i=k-1 before returning the value of k, which is now the total number of unique elements in the array.

Code Implementation

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
  
    public static void removeDuplicates(int a[], int n)
    {
        Set<Integer> hash_set = new HashSet<Integer>();
        for (int i = 0; i<n; i++) {
            hash_set.add(a[i]);
        }  
        System.out.print(hash_set);
        
    }
    public static void main(String[] args)
    {
        int a[] = {1,2,1,2,3,4,5,6,4,4,5,5};
        int n = a.length;
        removeDuplicates(a, n);
    }
}

Output

[1, 2, 3, 4, 5, 6]

Complexity Analysis

Time Complexity

• The first stage involves running a loop from i=0 to i=n-1 to put all of the array’s elements into the set. This will take O(N) time.
• The set internally employs hashing, and sorting the elements takes O(NlogN) time.
• In the worst case (assuming each element is unique), traversing the set will take O(N) time.

To remove duplicates from an array, this method’s worst-case time complexity is O(N)+O(NlogN)+O(N)=O(NlogN).

Space Complexity: This method involves utilizing a set and adding each element of the array to the set. Therefore, in this strategy, we are consuming O(N) auxiliary space.

Time Complexity: O(NlogN)
Auxiliary Space: O(N)

Method 4: Removing Duplicate Elements from an Array Using Frequency Array

If the range of the numbers in the array is small, we can utilize the frequency array; if the range is high, we can also use a set or map interface to eliminate duplicates.

Approach:

1. Find the array’s greatest number of elements (m).
2. Make a new array that is m+1 in size.
3. Next, go over the input array and count the frequency of each element.
4. Now, iterate through the frequency array and determine whether each number’s frequency is greater than 0. If it is, then print the corresponding number.

Code Implementation

import java.util.*;
 
class PrepBytes {
    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 + " ");
            }
        }
    }
}

Output

2 5 6 7 8

Complexity Analysis:

Time Complexity: O(n)
Auxiliary Space: O(m)

Method 5: Removing Duplicate Elements from an Array Using HashMap

If the number is higher than 106 or if the array consists of strings, the aforementioned frequency approach will be useless. In this situation, HashMap is required.

Approach:

1. Make a hashmap to hold the distinctive components.
2. Explore the collection.
3. Verify the HashMap to see if the element is there.
4. If so, navigate the array once more.
5. Else Print the element and add it to the hash map.

Code Implementation

import java.util.HashMap;
 
class PrepBytes {
    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);
    }
}

Output

1 2 5 7 4

Complexity Analysis:

Time Complexity: O(n)
Auxiliary Space: O(m)

Summary:
In this quick tutorial, we have discussed 5 different approaches to remove duplicates from arrays in Java.

• Removing Duplicate Elements from an Array Using Extra Space
• Removing Duplicate Elements from an Array Using Constant Extra Space
• Removing Duplicate Elements from an Array Using Set
• Removing Duplicate Elements from an Array Using Frequency array
• Removing Duplicate Elements from an Array Using HashMap

FAQ related to Removing Duplicate Elements from an Array in Java

Q1. What are duplicate elements in an array?
Ans. Duplicate elements in an array are values that occur more than once in the array.

Q2. Why is it important to remove duplicate elements from an array?
Ans. Removing duplicate elements from an array helps in simplifying and optimizing the data structure, making it easier to process and analyze.

Q3. What is the basic approach to removing duplicate elements from an array in Java?
Ans. The basic approach involves iterating over the array and checking each element against the previous elements. If a duplicate element is found, it is removed from the array.

Q4. What are some of the methods that can be used to remove duplicate elements from an array in Java?
Ans. Some of the methods that can be used to remove duplicate elements from an array in Java include using a HashSet, using a TreeSet, and using a for loop with an if statement.

Q5. How does using a HashSet help in removing duplicate elements from an array in Java?
Ans. A HashSet is a data structure that allows for efficient insertion, deletion, and lookup of elements. By adding each element of the array to a HashSet, duplicates are automatically removed.