June 22, 2022

Java Program to Remove Duplicate Elements From an Array

This post shows various ways to remove duplicate elements from an array in Java. The options you have are as follows-

  1. Create a LinkedHashSet by passing the array. Since Set only stores unique elements so duplicates are automatically removed by this process. Since LinkedHashSet maintains the insertion order so array element sequence too would not be disturbed. See example.
  2. Write your own logic in Java to remove duplicate elements from an array. See example.
  3. Using distinct() method of the Java Stream API you can remove duplicate elements from an array. This option is available Java 8 onward. See example.

Removing duplicates from an array using LinkedHashSet

public class RemoveDuplicates {
  public static void main(String[] args) {
    int[] numArr = {1, 1, 6, 7, 56, 9, 1, 23, 56, 7, 9, 10, 10};
    System.out.println("Original Array- " + Arrays.toString(numArr));
    int[] tempArr = findAndRemoveDuplicates(numArr);
    System.out.println("After removing duplicates- " + Arrays.toString(tempArr));
  }

  public static int[] findAndRemoveDuplicates(int[] numArr){
    // creating List from array
    List<Integer> numList = new ArrayList<Integer>();
    for(int i : numArr){
      numList.add(i);
    }
    Set<Integer> set = new LinkedHashSet<Integer>(numList);
    // Putting elements back in array
    int[] tempArray = new int[set.size()];
    int j =0;
    for(int num:set){
      tempArray[j++] = num;
    }
    return tempArray;
  }
}
Output
Original Array- [1, 1, 6, 7, 56, 9, 1, 23, 56, 7, 9, 10, 10]
After removing duplicates- [1, 6, 7, 56, 9, 23, 10]

As you can see from the output, because of using LinkedHashSet, ordering of the elements in array is not changed.

Removing duplicates from an array Java program – Own logic

If you are not supposed to use any Java Collection API or any other Java API for that matter then you can write your own logic to pick one element of the array at a time and scan the whole array in another inner loop to check if that element is repeated. If yes you need to remove it.

Removing element from array would require some work as array is of fixed size once created. So removing an element means shifting all the elements, which are after the removed element, to the left to fill that gap. But there is another problem once you shift elements to the left a space is created at the end of the array. To overcome that problem you need to keep track of how many elements are removed and reduce array size accordingly. With that reduced size create a new array and copy elements from original array with in the range 0 – reduced size.

To see various options to remove element from an array, please refer this post- Remove Element From an Array in Java

Following program remove duplicates from an array and also retains the order of the array.

public class RemoveDuplicates {
  public static void main(String[] args) {
    int[] numArr = {6, 6, 4, 15, 7, 6, 12, 7, 12, 12, 3, 8};
    System.out.println("Original Array- " + Arrays.toString(numArr));
    int[] tempArr = findAndRemoveDuplicates(numArr);
    System.out.println("After removing duplicates- " + Arrays.toString(tempArr));
  }
	
  public static int[] findAndRemoveDuplicates(int[] numArr){
    int size = numArr.length;
    for(int i = 0; i < size; i++){
      // for each element check for duplicates
      for(int j = i+1; j < size;){
        if(numArr[i] == numArr[j]){
          // shift elements to the left to remove duplicate
          for(int k = j; k < size-1; k++){
            numArr[k] = numArr[k+1];
          }
          size = size - 1;
        }else{
          j++;
        }
      }
    }
    // create temp array of reduced size
    int[] tempArray = new int[size];
    // copy array elements
    System.arraycopy(numArr, 0, tempArray, 0, size);
    return tempArray;
  }
}
Output
Original Array- [6, 6, 4, 15, 7, 6, 12, 7, 12, 12, 3, 8]
After removing duplicates- [6, 4, 15, 7, 12, 3, 8]

If you have a sorted array then you can use following program to remove duplicates from an array. This code uses only a single loop thus reducing the time complexity.

Logic here is to have to two variables to compare adjacent array elements (0 and 1 to start with) if elements are equal then increment one of the variable. Swap elements only when elements are not equal, that way duplicate elements are pushed to the right.

Then create a temp array with reduced size to keep only the unique elements.

public class RemoveDuplicates {
  public static void main(String[] args) {
    //int[] numArr = {4, 6, 6, 4, 15, 7, 6, 12, 7, 12, 12, 3, 8};
    int[] numArr = {1, 1, 1, 6, 7, 7, 9, 9, 10, 10, 23, 56, 56};
    System.out.println("Original Array- " + Arrays.toString(numArr));
    int[] tempArr = findAndRemoveDuplicates(numArr);
    
    System.out.println("After removing duplicates- " + Arrays.toString(tempArr));
  }
	
  public static int[] findAndRemoveDuplicates(int[] numArr){
    int i = 1;
    int j = 0;
    while(i < numArr.length){
      if(numArr[i] == numArr[j]){
        i++;
      }else{
        numArr[++j] = numArr[i++];
      } 
    }
    //create temp array with reduced size
    int[] tempArray = Arrays.copyOf(numArr, j+1);
    return tempArray;
  }
}

Removing duplicates from sorted array using Java Streams

Java 8 onward you can also use distinct() method of the Java Stream API to remove duplicates from an array in a very compact way.

distinct() method returns a stream consisting of the distinct elements, for duplicated elements, the element appearing first in the encounter order is preserved.

public class RemoveDuplicates {
  public static void main(String[] args) {
    int[] numArr = {4, 6, 6, 4, 15, 7, 6, 12, 7, 12, 12, 3, 8};
    System.out.println("Original Array- " + Arrays.toString(numArr));
    int tempArray[] = Arrays.stream(numArr).distinct().toArray();	
    System.out.println("After removing duplicates- " + Arrays.toString(tempArray));
  }
}
Output
Original Array- [4, 6, 6, 4, 15, 7, 6, 12, 7, 12, 12, 3, 8]
After removing duplicates- [4, 6, 15, 7, 12, 3, 8]

That's all for the topic Java Program to Remove Duplicate Elements From an Array. If something is missing or you have something to share about the topic please write a comment.


You may also like

No comments:

Post a Comment