Removing duplicates in an array

Problem: Remove duplicates from a given array of integers.

An important part of programming interviews is asking clarifying questions, and try to not assume anything. For example:

• What kind of values are we talking about?
• What is the range of possible values?
• Is the array sorted?
• How many values are there?
• How many duplicate values are there?
• Do you need to preserve the order of the elements that are not removed?

Depending on the answers, you may have a very different problem to solve. For example if the range of values is limited to [1:100], or if the array is sorted.

My gut reaction is to assume that the values are in the full range of valid integers, the array is not sorted, and there may be any number of duplicate values. However, during an interview it's important to not assume anything. Whether the candidate asks clarifying questions or just quietly makes assumptions can make a big difference. (How many times do programmers think they know what system they are supposed to build but they don't really know? Lots of times!)

My main goal in writing this code was in the mindset that I am in an interview and that I am given only 20 minutes to solve this problem.

It's usually ok to make something work the easiest possible way and then gradually make it better. In this example the easiest solution seems to be to iterate into a set and then convert that to an array.

public int[] removeDuplicate(int[] arr) {
    return toIntArray(toSet(arr));
}

private Set<Integer> toSet(int[] arr) {
    Set<Integer> set = new LinkedHashSet<>();
    for (int num : arr) {
        set.add(num);
    }
    return set;
}

private int[] toIntArray(Set<Integer> set) {
    int[] result = new int[set.size()];
    int i = 0;
    for (int num : set) {
        result[i++] = num;
    }
    return result;
}

Code review

Using the boolean literals true and false in conditions like this can be a red flag:

if (check[i] != true)

Use boolean expressions directly:

if (!check[i])

This is manual array copy:

    int returnArray[] = new int[index];

    for(int i = 0; i < returnArray.length; i++)
        returnArray[i] = temp[i];

    return returnArray;

It's recommended to use System.arraycopy or Arrays.copyOf instead. In this example you can replace the above lines with this one:

    return Arrays.copyOf(temp, index);

temp is a very poor name. Almost anything would be better, how about unique. With index renamed to uniqueCount, you end up with something quite natural:

    return Arrays.copyOf(unique, uniqueCount);

This version does not need a temp array for storing the result temporary, but I think its a bit more readable (potentially an opinion). The downside is that it will transverse the input array when populating the result array, while yours only iterates returnArray.length

public static int[] removeDups(int[] arg) {
    boolean[] isDup = new boolean[arg.length];
    int uniquesLength = arg.length;

    for(int i = 0; i < arg.length; i++) {
        if(!isDup[i]) {
            for (int k = i + 1; k < arg.length; k++) {
                if(!isDup[k] && arg[i] == arg[k]) {
                    isDup[k] = true;
                    uniquesLength--;    
                }
            }
        }
    }
    int[] uniques = new int[uniquesLength];
    int uniquesIndex = 0;

    for(int r = 0; r < arg.length; r++) {
        if(!isDup[r]) {
            uniques[uniquesIndex++] = arg[r];
        }   
    }
    return uniques;
}

I don't mean to say this code is better, because since you are concerned with time complexity, my version is worse (in that sense) because it will transverse the argument array one more time, while your version only transverses the (possibly) smaller result arrays length.

It can be done with less memory, and still fall within the same time complexity order.

On having better readability, I think not having a temp array makes the code clearer. And other posters already pointed out the importance of having meaningful variable names (which also made me correct my own variable names).

Although you said this method should work without Set, you also mentionned that you would love to see one solution with a HashSet.

In Java 8, very concise but not very efficient (behind the hoods, there is a boxing/unboxing operation for each element).

public int[] removeDuplicate(int[] arr) {
    return Arrays.stream(arr)
            .distinct()
            .toArray();
}