Remove duplicates from an array in Java

This is also one of the famous questions that is asked in big tech companies.

The goal is to remove all duplicate elements from an input array. 

There are several ways we can do that:

1. Using extra space
2. Without using extra space (in-place removal)
3. Using Set
4. Using Map

1. Removing duplicates from an array using extra space

Here, we'll create a new array and put only the unique elements in it. 

Note: This is only when the array is sorted - so either we receive the sorted array, or we sort it inside the method, for this approach to work.

public static void main(String[] args) {
int[] arr = {9, 3, 2, 3, 7, 9, 1, 10, 12, 1, 12, 4, 2, 5};
int[] newArr = new int[arr.length];

int index = removeDuplicates(arr, newArr);

// since the newArr contains zeros as trailing elements,
// we want to iterate only until we reach the index of j
for (int i = 0; i < index; i++) {
System.out.print(newArr[i] + " ");
}
}

public static int removeDuplicates(int[] arr, int[] newArr) {
Arrays.sort(arr); // sort the array
int j = 0;

for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] != arr[i + 1]) {
newArr[j++] = arr[i];
}
}

return j;
}

2. Removing duplicates with no extra space

Here, we use the same array, just keep track of the index (counter j) and we move unique elements at the beginning of the array.

public static void main(String[] args) {
int[] arr = {9, 3, 2, 3, 7, 9, 1, 10, 12, 1, 12, 4, 2, 5};
int index = removeDuplicates(arr);

//Since we moved the unique element at the beginning of the array,
//we want to iterate only until we reach the index of j
for (int i = 0; i < index; i++) {
System.out.print(arr[i] + " ");
}
}

public static int removeDuplicates(int[] arr) {
Arrays.sort(arr); // sort the array
int j = 0;

for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] != arr[i + 1]) {
arr[j++] = arr[i];
}
}

return j;
}

3. Removing duplicates using Set

Here, we'll be using the Set data structure, since Set can not contain duplicates. This is a good approach for an unsorted array.
If we try to add an element that already exists in a set, it will be discarded.

public static Object[] removeDuplicates(Object[] arr) {
//Use LinkedHashSet to maintain the insertion order
Set<Integer> set = new LinkedHashSet<>();

for (int i = 0; i < arr.length; i++) {
set.add((Integer) arr[i]);
}

return set.toArray();
}

4. Removing duplicates using Map

This is not the optimal solution, since we are creating a HashMap and a ArrayList and we also convert a list to array at the end.

public static Object[] removeDuplicates(int[] arr) {
Map<Integer, Integer> map = new LinkedHashMap<>();

for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
map.put(arr[i], map.get(arr[i]) + 1);
} else {
map.put(arr[i], 1);
}
}

List<Integer> list = new ArrayList<>();

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
list.add(entry.getKey());
}
}

return list.toArray();
}

That is all about how to remove duplicates from an array in Java.