Removing duplicates in an array Problem: Remove duplicates from a given array of integers.

I want this method to work without using data sets except an array.

My code is currently \$O(n^2 + n) = O(n^2)\$. How do I shorten this? 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. Thus, I tried to find the quickest way of solving the problem. Advice on how better to approach these problems would also be very helpful!

public int[] removeDuplicate(int[] arr)
{
    int temp[] = new int[arr.length];
    boolean[] check = new boolean[arr.length];
    int index = 0;
    for(int i = 0; i &lt; arr.length; i++)
    {
        if(check[i] != true)
            temp[index++] = arr[i];
        else
            continue;

        int var = arr[i];
        for(int j = i+1; j &lt; arr.length; j++)
        {
            if(var == arr[j])
                check[j] = true;
        }
    }
    int returnArray[] = new int[index];

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

    return returnArray;
}
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&lt;Integer&gt; toSet(int[] arr) {
    Set&lt;Integer&gt; set = new LinkedHashSet&lt;&gt;();
    for (int num : arr) {
        set.add(num);
    }
    return set;
}

private int[] toIntArray(Set&lt;Integer&gt; 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 &lt; 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);