Table of contents
1.
Introduction
2.
Using Extra Space
2.1.
Java
3.
Constant Extra Space
3.1.
Java
4.
Using Set
4.1.
Java
5.
Using Frequency Array
5.1.
Java
6.
Using HashMap
6.1.
Java
7.
Frequently Asked Questions
7.1.
What is the time complexity of removing duplicates from an array using extra space?
7.2.
Can we remove duplicates from an array without using any extra space?
7.3.
Does using a HashMap guarantee the order of elements in the resulting array?
8.
Conclusion
Last Updated: Aug 23, 2024
Medium

Remove Duplicates From Array in Java

Author Gaurav Gandhi
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Arrays are an important data structure in Java that allow us to store multiple elements of the same data type. However, sometimes we may encounter arrays that contain duplicate elements, which can lead to inefficiencies and errors in our programs. 

Remove Duplicates From Array in Java

In this article, we will discuss different techniques to remove duplicates from an array in Java, like using extra space, constant extra space, sets, frequency arrays, and hash maps.

Using Extra Space

One approach to remove duplicates from an array is by using extra space. In this method, we create a new array to store the unique elements. We iterate through the original array and add each element to the new array if it doesn't already exist in the new array. 

For example : 

  • Java

Java

import java.util.*;

public class RemoveDuplicates {

   public static int[] removeDuplicates(int[] arr) {

       ArrayList<Integer> uniqueList = new ArrayList<>();

      

       for (int i = 0; i < arr.length; i++) {

           if (!uniqueList.contains(arr[i])) {

               uniqueList.add(arr[i]);

           }

       }

       int[] uniqueArray = new int[uniqueList.size()];

       for (int i = 0; i < uniqueList.size(); i++) {

           uniqueArray[i] = uniqueList.get(i);

       }

      

       return uniqueArray;

   }   

   public static void main(String[] args) {

       int[] originalArray = {1, 2, 3, 2, 4, 3, 5};

       int[] uniqueArray = removeDuplicates(originalArray);

      

       System.out.println("Original Array: " + Arrays.toString(originalArray));

       System.out.println("Array with Duplicates Removed: " + Arrays.toString(uniqueArray));

   }

}
You can also try this code with Online Java Compiler
Run Code


Output

Original Array: [1, 2, 3, 2, 4, 3, 5]
Array with Duplicates Removed: [1, 2, 3, 4, 5]


In this code : 


We create an `ArrayList` called `uniqueList` to store the unique elements. We iterate through the original array using a `for` loop and check if each element already exists in `uniqueList` using the `contains()` method. If the element is not present, we add it to `uniqueList`.


After adding all the unique elements to `uniqueList`, we create a new array called `uniqueArray` with the same size as `uniqueList`. We then copy the elements from `uniqueList` to `uniqueArray` using another `for` loop.


Finally, we return the `uniqueArray` containing only the unique elements.


Note: This approach is straightforward and easy to understand. However, it requires extra space to store the unique elements in a separate data structure before copying them back to a new array.

Constant Extra Space

Another approach to remove duplicates from an array is by using constant extra space. In this method, we modify the original array in-place without using any additional data structures. We iterate through the array and compare each element with its previous elements. If a duplicate is found, we skip it and move on to the next element. 

For example : 

  • Java

Java

public class RemoveDuplicates {

   public static int removeDuplicates(int[] arr) {

       if (arr.length == 0) {

           return 0;

       }       

       int uniqueCount = 0;       

       for (int i = 1; i < arr.length; i++) {

           if (arr[i] != arr[uniqueCount]) {

               uniqueCount++;

               arr[uniqueCount] = arr[i];

           }

       }

      

       return uniqueCount + 1;

   }   

   public static void main(String[] args) {

       int[] array = {1, 2, 2, 3, 4, 4, 4, 5, 5};

       int uniqueCount = removeDuplicates(array);       

       System.out.println("Array with Duplicates Removed:");

       for (int i = 0; i < uniqueCount; i++) {

           System.out.print(array[i] + " ");

       }

   }

}
You can also try this code with Online Java Compiler
Run Code


Output

Array with Duplicates Removed:
1 2 3 4 5


In this code : 


We start by checking if the array is empty. If it is, we return 0 since there are no elements to process.


We initialize a variable called `uniqueCount` to keep track of the count of unique elements. We start iterating from index 1 of the array using a `for` loop.


Inside the loop, we compare the current element `arr[i]` with the element at index `uniqueCount`. If they are different, it means we have found a new unique element. We increment `uniqueCount` and update `arr[uniqueCount]` with the current element `arr[i]`.


If the elements are the same, it means we have encountered a duplicate, so we simply skip it and move on to the next element.


After the loop ends, `uniqueCount` will represent the count of unique elements in the array. We return `uniqueCount + 1` since the last unique element is not included in the count.


In the `main` method, we create an array with duplicates and call the `removeDuplicates` method. We then print the array with duplicates removed by iterating from index 0 to `uniqueCount - 1`.


Note: This approach modifies the original array in-place and uses constant extra space. However, it requires the array to be sorted in order to compare adjacent elements effectively.

Using Set

A straightforward approach to remove duplicates from an array is by using a set data structure. In Java, we can use the `HashSet` class, which stores unique elements and automatically eliminates duplicates. 

For example : 

  • Java

Java

import java.util.*;

public class RemoveDuplicates {

   public static Integer[] removeDuplicates(int[] arr) {

       Set<Integer> uniqueSet = new HashSet<>();       

       for (int num : arr) {

           uniqueSet.add(num);

       }

      

       return uniqueSet.toArray(new Integer[0]);

   } 

   public static void main(String[] args) {

       int[] originalArray = {1, 2, 3, 2, 4, 3, 5};

       Integer[] uniqueArray = removeDuplicates(originalArray);       

       System.out.println("Original Array: " + Arrays.toString(originalArray));

       System.out.println("Array with Duplicates Removed: " + Arrays.toString(uniqueArray));

   }

}
You can also try this code with Online Java Compiler
Run Code

 

Output

Original Array: [1, 2, 3, 2, 4, 3, 5]
Array with Duplicates Removed: [1, 2, 3, 4, 5]


In this code : 

we create a `HashSet` called `uniqueSet` to store the unique elements. We iterate through the original array using an enhanced `for` loop and add each element to `uniqueSet` using the `add()` method. The `HashSet` automatically takes care of removing duplicates.


After adding all the elements to `uniqueSet`, we convert it back to an array using the `toArray()` method. Since `HashSet` stores objects, we need to specify the type of the array as `Integer[]`.


Finally, we print the original array and the array with duplicates removed using `Arrays.toString()` for a readable output.


Note: set method is an efficient way to remove duplicates as it provides constant-time performance for adding and checking elements. However, it does require extra space to store the unique elements in the set.


Point to Remember : Keep in mind that using a set may not preserve the original order of the elements in the array. If maintaining the order is important, you can consider using a `LinkedHashSet` instead, which preserves the insertion order of the elements.

Using Frequency Array

Another approach to remove duplicates from an array is by using a frequency array. In this method, we create an additional array to keep track of the frequency of each element in the original array. We iterate through the original array and mark the frequency of each element in the frequency array. Then, we create a new array and copy the elements with a frequency of 1 from the original array to the new array. 

For example : 

  • Java

Java

public class RemoveDuplicates {

   public static int[] removeDuplicates(int[] arr) {

       int max = Arrays.stream(arr).max().getAsInt();

       int[] frequencyArray = new int[max + 1];

      

       for (int num : arr) {

           frequencyArray[num]++;

       }       

       int uniqueCount = 0;

       for (int i = 0; i < frequencyArray.length; i++) {

           if (frequencyArray[i] == 1) {

               uniqueCount++;

           }

       }       

       int[] uniqueArray = new int[uniqueCount];

       int index = 0;

       for (int i = 0; i < frequencyArray.length; i++) {

           if (frequencyArray[i] == 1) {

               uniqueArray[index] = i;

               index++;

           }

       }       

       return uniqueArray;

   }   

   public static void main(String[] args) {

       int[] originalArray = {1, 2, 3, 2, 4, 3, 5};

       int[] uniqueArray = removeDuplicates(originalArray);

      

       System.out.println("Original Array: " + Arrays.toString(originalArray));

       System.out.println("Array with Duplicates Removed: " + Arrays.toString(uniqueArray));

   }

}
You can also try this code with Online Java Compiler
Run Code

 

Output

Original Array: [1, 2, 3, 2, 4, 3, 5]
Array with Duplicates Removed: [1, 2, 3, 4, 5]


In this code : 

We start by finding the maximum element in the original array using `Arrays.stream(arr).max().getAsInt()`. We create a frequency array called `frequencyArray` with a size equal to `max + 1` to accommodate all possible elements.

We iterate through the original array using an enhanced `for` loop and increment the frequency of each element in `frequencyArray`. For example, if the element is 2, we increment `frequencyArray[2]` by 1.

After updating the frequencies, we count the number of unique elements by iterating through `frequencyArray` and counting the elements with a frequency of 1. We store the count in the `uniqueCount` variable.

Next, we create a new array called `uniqueArray` with a size equal to `uniqueCount` to store the unique elements. We iterate through `frequencyArray` again and copy the elements with a frequency of 1 from the original array to `uniqueArray`. We use a separate index variable to keep track of the position in `uniqueArray`.

Finally, we return `uniqueArray` containing only the unique elements.

Note: This approach uses a frequency array to keep track of the count of each element. It requires extra space proportional to the maximum element in the array. However, it does not require the array to be sorted and preserves the order of the unique elements.

Using HashMap

Another efficient approach to remove duplicates from an array is by using a HashMap. In Java, a HashMap is a data structure that stores key-value pairs, allowing us to quickly check if an element already exists. 

For example : 

  • Java

Java

import java.util.*;

public class RemoveDuplicates {

   public static int[] removeDuplicates(int[] arr) {

       HashMap<Integer, Boolean> uniqueMap = new HashMap<>();

      

       for (int num : arr) {

           uniqueMap.put(num, true);

       }       

       int[] uniqueArray = new int[uniqueMap.size()];

       int index = 0;

       for (int num : uniqueMap.keySet()) {

           uniqueArray[index] = num;

           index++;

       }

      

       return uniqueArray;

   }   

   public static void main(String[] args) {

       int[] originalArray = {1, 2, 3, 2, 4, 3, 5};

       int[] uniqueArray = removeDuplicates(originalArray);      

       System.out.println("Original Array: " + Arrays.toString(originalArray));

       System.out.println("Array with Duplicates Removed: " + Arrays.toString(uniqueArray));

   }

}
You can also try this code with Online Java Compiler
Run Code


Output

Original Array: [1, 2, 3, 2, 4, 3, 5]
Array with Duplicates Removed: [1, 2, 3, 4, 5]


In this code : 

We create a `HashMap` called `uniqueMap` to store the unique elements as keys and a boolean value as the associated value. We iterate through the original array using an enhanced `for` loop and add each element to `uniqueMap` using the `put()` method. If an element already exists in the map, it will be overwritten, effectively removing duplicates.


After adding all the elements to `uniqueMap`, we create a new array called `uniqueArray` with a size equal to the number of key-value pairs in `uniqueMap`, which represents the count of unique elements.
 

We iterate through the key set of `uniqueMap` using an enhanced `for` loop and copy each key (unique element) to `uniqueArray`. We use a separate index variable to keep track of the position in `uniqueArray`.


Finally, we return `uniqueArray` containing only the unique elements.


Note: HashMap method provides an efficient way to remove duplicates as it offers constant-time performance for adding and checking elements. However, it does require extra space to store the key-value pairs.


Point to remember : Always remember that  HashMap method does not guarantee any specific order of the elements in the resulting array. If maintaining the order is important, you can consider using a `LinkedHashMap` instead, which preserves the insertion order of the elements.

Frequently Asked Questions

What is the time complexity of removing duplicates from an array using extra space?

The time complexity of removing duplicates using extra space is O(n), where n is the number of elements in the array. This is because we need to iterate through the array once to add elements to the new data structure and then copy the unique elements back to a new array.

Can we remove duplicates from an array without using any extra space?

Yes, it is possible to remove duplicates from an array without using any extra space by modifying the array in-place. The approach using constant extra space achieves this by comparing each element with its previous elements and skipping duplicates. However, this approach requires the array to be sorted.

Does using a HashMap guarantee the order of elements in the resulting array?

No, using a HashMap does not guarantee any specific order of the elements in the resulting array. The order of elements in a HashMap is not predictable. If maintaining the order is important, you can use a LinkedHashMap instead, which preserves the insertion order of the elements.

Conclusion

In this article, we explained different techniques to remove duplicates from an array in Java. We started by using extra space to store unique elements in a new array. Then, we discussed the approach of using constant extra space to modify the array in-place. We also explained this using sets, frequency arrays, and hash maps to efficiently remove duplicates.
You can also check out our other blogs on Code360.

Live masterclass