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 < arr.length; i++)    {        if(check[i] != true)            temp[index++] = arr[i];        else            continue;        int var = arr[i];        for(int j = i+1; j < arr.length; j++)        {            if(var == arr[j])                check[j] = true;        }    }    int returnArray[] = new int[index];    for(int i = 0; i < returnArray.length; i++)        returnArray[i] = temp[i];    return returnArray;}
Removing duplicates in an array
java;algorithm;array
Your algorithm is relatively clear to see, and it makes sense, and it works. In an interview, these are good things.Your algorithm is an \$O(n^2)\$ algorithm in time complexity - for every value in the array, you effectively check every other value for duplication.There are a couple of things I would note here, though.The check array is unnecessary. Instead of marking all 'future' duplicates of the value, why don't you check all processed values so far? Consider this inner loop:boolean dup = false;for (int j = 0; j < index, j++) {    if (temp[j] == value) {        dup = true;        break;    }}if (!dup) {    temp[index++] = value;}The above loop also allows you to enhance the outer for-loop:for (int value : arr) {    ....}The above algorithm is also an \$O(n^2)\$ one, but it will likely run faster for 2 reasons:It breaks early if it finds a duplicateThe inner loop only processes unique values, not all values.As an aside, if the order of the output values is not important, I would consider keeping the temp array as a sorted array.... and using Arrays.binarySearch(...). This will make the algorithm complexity a bit more complex ... something in between \$O(n \log n)\$ and \$O(n^2)\$.... profiling would be required to see if it is an actual improvement.....for (int value : arr) {    int ip = Arrays.binarySearch(temp, 0, index, value);    if ip >= 0 {        // duplicate        continue;    }    // insert value in to temp in the sorted order.    ip = -ip - 1;    System.arrayCopy(temp, ip, temp, ip + 1, index - ip);    temp[ip] = value;    index++;}The binary search is a \$O(\log n)\$ operation, and the array-copy is a hard thing to quantify in terms of n because it depends.Anyway, food for thought.Of course, you could just sort the array, and then skip duplicates that way... it would make it a more apparent \$O(n \log n)\$ operation.