Thursday, June 20, 2019

Remove Duplicate Elements From an Array in Java

Write a Java program to remove duplicate elements from an array is a frequently asked interview question and you may be asked to do it without using any of the collection data structure like List or Set or you may be asked to do it using Collection API classes first and then without using any of those classes.

In this post we’ll see Java programs for removal of duplicate elements in an array using Collection API classes, without Collection API and using Java Stream API.

Using Collection API

One way to remove duplicate elements from an array in Java is to copy your array elements to a HashSet. As you know HashSet only stores unique elements so any repetition of an element will be discarded. Using this property of HashSet once you copy all the array elements to a HashSet you’ll have a Set with only unique elements. Now you can again copy the elements from your Set to create an array which will be your array with duplicate elements removed.

Remove Duplicate Elements From an Array using HashSet

 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateRemoval {

  public static void main(String[] args) {
    int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
    int[] outArr = removeDuplicatesUsingSet(intArr);
    System.out.println("Original array");
    for(int i : intArr){
      System.out.print(i+" ");
    }
    System.out.println("");
    System.out.println("after removal");
    for(int i : outArr){
      System.out.print(i+" ");
    }
  }
    
  /**
  * @param input
  * @return
  */
  public static int[] removeDuplicatesUsingSet(int[] input){
    // Adding array elements to a list
    List<Integer> tempList = new ArrayList<Integer>();
    for(int i : input){
      tempList.add(i);
    }
    // creating a set using list     
    Set<Integer> set = new HashSet<Integer>(tempList);
    Integer[] output = new Integer[set.size()];
    int[] arrOut = new int[output.length];
    set.toArray(output);
    int j =0;
    for(Integer i : output){
      arrOut[j++] = i;
    }
    return arrOut;
  }
}

Output

Original array
1 2 2 5 1 6 12 7 12 12 3 8 
after removal
1 2 3 5 6 7 8 12 

Few things to note here are-

  1. If you are using Set then ordering with in the array doesn’t matter i.e. Array doesn’t have to be sorted.
  2. Ordering of the original array will not be retained once elements are stored in the Set.
  3. In the above code I have used int[] array (array of primitives) that’s why there are some extra steps like creating Array of Integer[] (Integer objects) as toArray() method of the Set works only with objects. If you have an array of objects then you don’t need these extra steps.

Remove Duplicate Elements From an Array using LinkedHashSet

In the above Java code to delete element from an array using HashSet, ordering of the array elements is not retained, if you want ordering to be retained then use LinkedHashSet instead.

 
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class DuplicateRemoval {

  public static void main(String[] args) {
    int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
    int[] outArr = removeDuplicatesUsingSet(intArr);
    System.out.println("Original array");
    for(int i : intArr){
      System.out.print(i+" ");
    }
    System.out.println("");
    System.out.println("after removal");
    for(int i : outArr){
      System.out.print(i+" ");
    }
  }
    
  /** 
   * @param input
   * @return
   */
   public static int[] removeDuplicatesUsingSet(int[] input){
    // Adding array elements to a list
    List<Integer> tempList = new ArrayList<Integer>();
    for(int i : input){
      tempList.add(i);
    }
    // creating a set using list     
    Set<Integer> set = new LinkedHashSet<Integer>(tempList);
    Integer[] output = new Integer[set.size()];
    int[] arrOut = new int[output.length];
    set.toArray(output);
    int j =0;
    for(Integer i : output){
      arrOut[j++] = i;
    }
    return arrOut;
  }
}

Output

Original array
1 2 2 5 1 6 12 7 12 12 3 8 
after removal
1 2 5 6 12 7 3 8 

Now you can see ordering of the array elements is retained. For duplicate elements first occurrence of the element is retained.

Java Example without using Collection

If you have to remove duplicate elements of the array without using any of the Collection API classes then you can use the following code.

In the program input array is sorted first so that all the duplicate elements are adjacent to each other. By doing that you need only a single loop for comparison.
For removing duplicate elements you need to shift all the elements after the duplicate to the left. Another thing to note here is that array size is fixed once defined, when duplicate element is removed and you shift element after the duplicate to the left that creates space on the right side of the array. To remove that space you need to truncate the array by using copyOf() method of the Arrays utility class.

public class DuplicateRemoval1 {
  /** 
   * @param input
   * @return
  */
  public static int[] removeDuplicates(int[] intArr){
    int i = 1;
    int j = 0;
    Arrays.sort(intArr);
    System.out.println("Sorted array");
    for(int x : intArr){
      System.out.print(x+" ");
    }
    while(i < intArr.length){
      if(intArr[i] == intArr[j]){
        i++;
      }else{
        intArr[++j] = intArr[i++];
      }   
    }
    // This is required to truncate the size of the array
    // otherwise array will retain its original size
    int[] output = Arrays.copyOf(intArr, j+1);
    return output;
  }

  public static void main(String[] args) {
    int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
    int[] outArr = removeDuplicates(intArr);
    System.out.println("");
    System.out.println("after removal");
    for(int i : outArr){
      System.out.print(i+" ");
    }
  }
}

Output

Sorted array
1 1 2 2 3 5 6 7 8 12 12 12 
after removal
1 2 3 5 6 7 8 12 

Time and space complexity

As per the description of the Arrays.sort() method its time complexity is O(n*logn). Then array is traversed in the while loop which takes O(n) time thus the time complexity of the above code is O(n*logn+n).

Using Java Stream to remove duplicates from array

Java Stream API (From Java 8) also provides an option to remove duplicate elements from an array. You can use distinct() method to remove duplicate elements.

int[] intArr = {1, 2, 2, 5, 1, 6, 12, 7, 12, 12, 3, 8};
int tempArr[] = Arrays.stream(intArr).distinct().toArray();
       
System.out.println("");
System.out.println("after removal");
for(int i : tempArr){
 System.out.print(i+" ");
}

Output

after removal
1 2 5 6 12 7 3 8

That's all for this topic Remove Duplicate Elements From an Array in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. How to Remove Duplicate Elements From an ArrayList in Java
  2. Matrix Multiplication - Java Program
  3. Find Maximum And Minimum Numbers in The Given Matrix - Java Program
  4. How to Find Common Elements Between Two Arrays - Java Program
  5. Array in Java

You may also like-

  1. Splitting a String - Java Program
  2. Count Total Number of Times Each Character Appears in a String - Java Program
  3. How to read file from the last line in Java
  4. Unzipping files in Java
  5. Difference Between Comparable and Comparator in Java
  6. How HashMap internally works in Java
  7. Map operation in Java Stream API
  8. Java Concurrency Interview Questions And Answers