Friday, 16 June 2017

How to remove duplicate elements from an array - Java Program

How 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 code for removal of duplicate elements in an array using Collection API classes and without it.

Using Collection API

One way to remove duplicate elements from an array 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.

Example code with 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.

Example code with LinkedHashSet

In the above code with 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.

Example code 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.

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 

Few things to note here are -

  1. Array has to be sorted in order for this code to work properly that is why array is sorted using Arrays.sort() method.
  2. Once an array is created it will have a fixed size that is why Arrays.copyOf() method is used which can truncate the array to given size. That is required as array size may reduce after removing duplicates.

Time and space complexity

As per the description of the Arrays.sort() method its time complexity is O(n log(n)). Then array is traversed in the while loop and then array is copied. That time complexity will be O(2n) thus the time complexity of the above code is O(n log(n))+O(2n). While the space complexity is O(1).

Using Java Stream

Java Stream API (From Java 8) also provides an option to remove duplicate elements from an array.

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 How to remove duplicate elements from an array. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How to remove duplicate elements from an ArrayList in Java
  2. Matrix Multiplication Java Program
  3. How to Sort elements in different order in TreeSet
  4. Array in Java

You may also like -

>>>Go to Java Programs page

No comments:

Post a Comment