Remove Duplicates in a Java Array

As I go through interviews while looking for jobs, I often come home and revisit the questions as a learning experience. Here is an interview question that I often encounter: Given an array of integer where the elements (entries) are not sorted, write a function to return a new array with the duplicate entries removed. For example, if the original array is:

1,2,3,1,2,3

then the function should return:

1,2,3

The first time I tackled this problem, I did not make use of Java’s collections framework. As the result, the code are long, hard to read, and hard to maintain. When the interviewer asked me to improve the code, I finally thought of using the collections framework, but what kind of collection should I use? The interview was kind enough to provide me with a reference book for my research. To solve this problem, I need a collection that provides fast look-up, retains the original insertion order, and ignores the insertion of duplicate entries. As it turns out, Java collection framework does provide a collection that fit my demand and it is called LinkedHashSet. Using LinkedHashSet, I was able to simplify the code’s logic. For a complete listing of my code, follow the link here.

About these ads

11 thoughts on “Remove Duplicates in a Java Array

  1. Giordano

    Hi, i’m a kid from Italy, i’m 10 years old. I’m tryng to compile your solution (removing duplicates in a java array) but i still cannot understand how your class “RemoveDuplicatesEntries” can works if it hasn’t got any method-Main.
    Please can you write a little example (like mine posted below) where an Integer array, or better a String array, are initialized with duplicate values and then we can applicate your solution?
    Thanks so much,
    Giordano


    public class prova
    {
    public static void main(String[] args)
    {
    int[] an_array = {0,1,2,3,3,3,4,1,5,6,7,5};
    int[] tmp = new int[an_array.length];

    for (Integer i : an_array)
    System.out.print(i + " ");

    // ? RemoveDuplicatesEntries ?
    // CAN YOUR RemoveDuplicatesEntries WORKS ALSO WITH Strings array, chars array, Lists, Queues, Stacks... ??

    }
    }

    “Grazie mille!!” (Thanks one thousand time)

  2. wuhrr Post author

    How to call removeDuplicates()?
    The easiest way is to move removeDuplicates() into your class prova and call it as follow:

    int[] tmp = removeDuplicates(an_array);

    My solution does not work with other kind of array or collection.

  3. imi

    Better not use an static array, but some collection class. Example:

    List l = …
    for (int i = 1; i < l.size();) {
    if (l.subList(0,i-1).contains(l.get(i)))
    l.remove(i);
    else
    i++;
    }

    Awefull slow on lists with lot of elements (especially on linked lists). But works fine for <1000 elements..

  4. Podanga

    Use collections, for example,

    public static void main(String[] argz) {
    try {
    String[] policyNumbers = new String[] { “12345678”, “16018189”
    , “12345678”, “16018189”, ” 12345678″, ” 16018189 “};

    String[] refinedPolicies = removeDuplicates(policyNumbers);
    log(“refinedPolicies size:” + refinedPolicies.length);

    } catch (Exception e) {
    e.printStackTrace();
    }
    }

    private static String[] removeDuplicates(String[] stringArray){

    if( stringArray == null && stringArray.length == 0){
    return stringArray;
    }

    ArrayList stringArrayList = new ArrayList();
    String trimmedString = null;

    for( int i=0; i0){

    if( !stringArrayList.contains(trimmedString)){
    stringArrayList.add(trimmedString);
    }
    }
    }

    String[] refinedStringArray = new String[stringArrayList.size()];
    stringArrayList.toArray(refinedStringArray);
    return refinedStringArray;

    }

  5. Podanga

    Note that the above code does not require any exception handling (in the main method) as there won’t be any checked exceptions thrown in this scenario.

  6. Earl

    The code above wouldn’t compile, here the code that works:

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    public class MergeStrings {
    public static void main(String[] argz) {
    try {
    String[] policyNumbers = new String[6];

    policyNumbers[0] = “12345678?;

    policyNumbers[0] = “16018189?;” +
    “, “12345678?, “16018189?, “12345678?, “16018189”};

    String[] refinedPolicies = removeDuplicates(policyNumbers);
    log(“refinedPolicies size:” + refinedPolicies.length);

    } catch (Exception e) {
    e.printStackTrace();
    }
    }

    private static String[] removeDuplicates(String[] stringArray){

    if( stringArray == null && stringArray.length == 0){
    return stringArray;
    }

    ArrayList stringArrayList = new ArrayList();
    String trimmedString = null;

    for( int i=0; i0){

    if( !stringArrayList.contains(trimmedString)){
    stringArrayList.add(trimmedString);
    }
    }
    }

    String[] refinedStringArray = new String[stringArrayList.size()];
    stringArrayList.toArray(refinedStringArray);
    return refinedStringArray;

    }
    }

  7. Mednikov Yury

    if u want it clean way with arrays only thats the best way

    public static boolean isUnique(int [] arry, int num)//Return true if number num is appeared only once in the array – num is unique.
    {
    for (int i = 0; i < arry.length;i++)
    {
    if (arry [i] == num)
    {
    return false;
    }
    }
    return true;
    }

    public static int[] toUniqueArray (int[] array)//Convert the given array to an array with unique values – without duplicates and Return it
    {
    int[]temp=new int[array.length];

    for(int i=0;i<temp.length;i++)
    {
    temp[i]=-1;// in case u have value of 0 in he array
    }
    int counter=0;

    for(int i=0;i<array.length;i++)
    {
    if(isUnique(temp,array[i]))
    temp[counter++]=array[i];
    }
    int []uniqueArray=new int[counter];

    System.arraycopy(temp, 0, uniqueArray, 0, uniqueArray.length);

    return uniqueArray;
    }
    public static void printArray(int[] array)// Print given array
    {
    for(int i=0;i<array.length;i++)
    {
    System.out.print(array[i]+" ");
    }

    System.out.println("");
    }

    public static void main(String[] args)
    {
    int[] array= {1, 1, 2, 3, 4, 1, 4, 7, 9, 7 };
    ArrayUtil.printArray(array);
    ArrayUtil.printArray(ArrayUtil.toUniqueArray(array));

    }

  8. Mednikov Yury

    two last lines is incorrect. the correct is
    printArray(array);
    printArray(toUniqueArray(array));

  9. Mednikov Yury

    public class UnuqueArray
    {
    public static boolean isUnique(int [] arry, int num)//Return true if number num is appeared only once in the array – num is unique.
    {
    for (int i = 0; i < arry.length;i++)
    {
    if (arry [i] == num)
    {
    return false;
    }
    }
    return true;
    }

    public static int[] toUniqueArray (int[] array)//Convert the given array to an array with unique values – without duplicates and Return it
    {
    int[]temp=new int[array.length];

    for(int i=0;i<temp.length;i++)
    {
    temp[i]=-1;// in case u have value of 0 in he array
    }
    int counter=0;

    for(int i=0;i<array.length;i++)
    {
    if(isUnique(temp,array[i]))
    temp[counter++]=array[i];
    }
    int []uniqueArray=new int[counter];

    System.arraycopy(temp, 0, uniqueArray, 0, uniqueArray.length);

    return uniqueArray;
    }

    public static void printArray(int[] array)// Print given array
    {
    for(int i=0;i<array.length;i++)
    {
    System.out.print(array[i]+" ");
    }

    System.out.println("");
    }

    public static void main(String[] args)
    {
    int[] array= {1, 1, 2, 3, 4, 1, 4, 7, 9, 7 };
    printArray(array);
    printArray(toUniqueArray(array));
    }

    }

  10. ASA

    The link for the complete code is broken, can you give us the actual link please? Thanks in advance

  11. Hai Post author

    @ASA: I apologize for the stale link. I have moved the code to bitbucket.org and updated the link. Please try again.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s