Remove duplicates from an array in Java

There are many ways to remove duplicates from an array in Java.

Sorted array

When an array is sorted, we can use the following solution:

public class DevPrimer {

  public static void main(String[] args) {
    int[] sortedArray = {1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 11, 11, 11, 12, 13,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 17, 17, 18};

    int n = removeFromSorted(sortedArray);

    for (int i = 0; i <= n; i++) {
      System.out.print(sortedArray[i] + " ");
    }
  }

  public static int removeFromSorted(int[] arr) {
    int j = 0;
    // add only the last element from the sequence of duplicate elements
    for (int i = 0; i < arr.length - 1; i++) {
      if (arr[i] != arr[i + 1]) {
        arr[j++] = arr[i];
      }
    }

    arr[j] = arr[arr.length - 1]; // add the last element

    return j;
  }
}

Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 

In the main method, we iterate over the array until we get to the index that the removeFromSorted method returns. 

If we would iterate until the end of the array, the output would be:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 12 13 14 14 14 14 14 14 14 14 14 14 15 17 17 18.

As you can see, the numbers after the 18 (bolded) are numbers that are leftovers from the original order of elements in the sortedArray.

So it is important to iterate until we get to the index that the removeFromSorted method returns.

If we don't want to do like this and we want to have an array with only unique elements, then we need to create another array.

The solution would be like this:

public class DevPrimer {

  public static void main(String[] args) {
    int[] sortedArray = {1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 11, 11, 11, 12, 13,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 17, 17, 18};

    int[] arrayWithoutDuplicates = removeFromSorted(sortedArray);

    Arrays.stream(arrayWithoutDuplicates).forEach(element -> System.out.print(element + " "));

  }

  public static int[] removeFromSorted(int[] arr) {
    int j = 0;
    int[] newArray;

    // add only the last element from the sequence of duplicate elements
    for (int i = 0; i < arr.length - 1; i++) {
      if (arr[i] != arr[i + 1]) {
        arr[j++] = arr[i];
      }
    }

    arr[j] = arr[arr.length - 1]; // add the last element

    // initialize the new array with length of j + 1
    newArray = new int[j + 1];

    // add numbers from arr to newArray - from index 0 to j
    for (int i = 0; i <= j; i++) {
      newArray[i] = arr[i];
    }

    return newArray;
  }
}
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18

This solution uses extra space - space complexity is O(n) but we get one clean array with only unique elements.
Time complexity is also O(n) - which is fine.

Removing duplicates from an array using Set

A Set is a data structure that can not contain duplicates. We can use it to store all the elements, and we will end up with a set that contains only unique elements - since when we try to add an element that already exists in a set - it will be discarded.

One important thing about HashSet is that it does not maintain insertion order, so it is best to use LinkedHashSet - to preserve the order of elements.

Here is the program:

public class DevPrimer {

  public static void main(String[] args) {
    int[] sortedArray = {1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 11, 11, 11, 12, 13,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 17, 17, 18};

    removeFromSorted(sortedArray).forEach(element -> System.out.print(element + " "));
  }

  public static Set<Integer> removeFromSorted(int[] arr) {
    Set<Integer> set = new LinkedHashSet<>();

    // enhanced for-loop
    for (int j : arr) {
      set.add(j);
    }

    return set;

  }
}

Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18

If we need to return an array, then we need to create a new array and populate it with the elements from the set.

The time complexity of this solution is O(n), and space complexity is also O(n) since we are creating a new data structure (Set) which requires additional space in memory. 

Removing duplicates from an array using Map

We can also use Map to solve this problem since Map contains only unique keys:

public class DevPrimer {

  public static void main(String[] args) {
    int[] sortedArray = {1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 11, 11, 11, 12, 13,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 17, 17, 18};

    removeFromSorted(sortedArray).keySet().forEach(key -> System.out.print(key + " "));
  }

  public static Map<Integer, Integer> removeFromSorted(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();

    // enhanced for-loop
    for (int j : arr) {
      map.put(j, null); // We are interested only in populating the keys. Value can be null for all elements
    }

    return map;
  }
}

Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18

Here, if we also need to return an array, then we need to create a new one and populate the elements from the map (keys only - using keySet()).

Note: the keySet() method creates (and returns) a set of the keys contained in the map.

Both time and space complexity is O(n).