Removing the duplicates from an array without disturbing the order of elements without using Sets

Question

I need a java code which can remove the duplicates from an array without changing the order of elements and without using Sets or the sort techniques.

eg: If input array is {23,1,5,4,2,23,6,2,4} Then output should be {23,1,5,4,2,6}

Answer 1

You can do it in O(n^2) time with O(1) extra space.

public static int[] noSpaceElementDistinctness(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n;i++) {
        boolean exists = false;
        for (int j = 0; j < i; j++) {
            if (arr[i] == arr[j]) {
                exists = true;
                break;
            }
        }
        if (exists) {
            for (int j = i+1; j<n; j++)
                arr[j-1] = arr[j];
        n--;
        i--; //to iterate the next element, which is now at index i, not i+1.
        }
    }
    for (int i = n; i < arr.length; i++) arr[i] = Integer.MIN_VALUE; //indicates no value
    return arr;

}

---

As a side note, the element distinctness problem is not that trivial to solve efficiently as it might seem from first glance, and it is one problem with strict lower bound of what you can do to solve it efficiently. This thread discusses it.

Answer 2

If you use Java 8 a simple way would be:

int[] array = {23, 1, 5, 4, 2, 23, 6, 2, 4};
int[] noDupes = IntStream.of(array).distinct().toArray();
System.out.println(Arrays.toString(noDupes)); // [23, 1, 5, 4, 2, 6]

Answer 3

Create a new ArrayList(). Loop over old list and copy the value to new unless it is already in it.

The order will be changed because you will not copy all...

Answer 4

There's several options - some more efficient than others:

/**
 * Brute force approach - very inefficient.
 *
 * Finds each duplicate and removes it.
 */
private int[] removeDupesUsingNoExtraMemory(int[] a) {
    int length = a.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if (a[i] == a[j]) {
                // No point copying if this is the last one.
                if (j < length - 1) {
                    // Remove a[j].
                    System.arraycopy(a, j + 1, a, j, length - j - 1);
                }
                length -= 1;
            }
        }
    }
    // Actually it does use extra memory but only to trim the array because Java cannot slice arrays.
    return Arrays.copyOf(a, length);
}

/**
 * A bit more efficient.
 *
 * Copies only non-duplicate ones.
 */
private int[] removeDupesDifferently(int[] a) {
    int length = a.length;
    // Copying to the end backwards.
    int to = length - 1;
    // Copy backwards so we remove the second duplicate - not the first.
    for (int i = length - 1; i >= 0; i--) {
        boolean duplicate = false;
        for (int j = 0; j < i && !duplicate; j++) {
            duplicate |= a[i] == a[j];
        }
        if (!duplicate) {
            a[to--] = a[i];
        }
    }
    return Arrays.copyOfRange(a, to + 1, a.length);
}

/**
 * Most efficient - but uses a `Set`.
 *
 * Builds a `Set` of `seen` values so we don't copy duplicates.
 */
private int[] removeDupesUsingASet(int[] a) {
    int to = 0;
    Set<Integer> seen = new HashSet<>();
    for (int i = 0; i < a.length - 1; i++) {
        // Seen it before?
        if (!seen.contains(a[i])) {
            a[to++] = a[i];
            // Seen that one - don't want to see it again.
            seen.add(a[i]);
        }
    }
    return Arrays.copyOf(a, to);
}

public void test() {
    System.out.println("removeDupesUsingNoExtraMemory = " + Arrays.toString(removeDupesUsingNoExtraMemory(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
    System.out.println("removeDupesDifferently = " + Arrays.toString(removeDupesDifferently(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
    System.out.println("removeDupesUsingASet = " + Arrays.toString(removeDupesUsingASet(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
}

Answer 5

    int arr[] = {23,1,5,4,2,6} ;
    List<Integer> list = new ArrayList<Integer>();
    for(int i = 0; i<arr.length; i++) {
        if (!list.contains(arr[i])) {
            list.add(arr[i]);
        }
    }

    Iterator it = list.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

Answer 6

If you just need to print the unique elements without modifying the array, you can do it with this alternative solution. Sort the array with O(n log n) (merge sort e.g.) and run through the array O(n) to print only elements that have their adjacent element different, that is:

if( arr[i] != arr[i + 1]) {
  print(arr[i]);
}

Cheers!