[Solved] algorithm removing duplicate elements in array without auxillay storage

Question

OK, here’s my answer, which should be O(N*N) worst case. (With smaller constant, since even worstcase I’m testing N against — on average — 1/2 N, but this is computer science rather than software engineering and a mere 2X speedup isn’t significant. Thanks to @Alexandru for pointing that out.)

1) Split cursor (input and output advanced separately),

2) Each new value only has to be compared to what’s already been kept, and compare can stop if a match is found. (The hint keyword was “incremental”)

3) First element need not be tested.

4) I’m taking advantage of labelled continue where I could have instead set a flag before breaking and then tested the flag. Comes out to the same thing; this is a bit more elegant.

4.5) I could have tested whether outsize==consider and not copied if that was true. But testing for it would take about as many cycles as doing the possibly-unnecessary copy, and the majority case is that they will not be the same, so it’s easier to just let a possibly redundant copy take place.

5) I’m not recopying the data in the key function; I’ve factored out the copy-for-printing operation to a separate function to make clear that removeDupes does run entirely in the target array plus a few automatic variables on the stack. And I’m not spending time zeroing out the leftover elements at the end of the array; that may be wasted work (as in this case). Though I don’t think it would actually change the formal complexity.

import java.util.Arrays;

public class RemoveDupes {

  private static int removeDupes(final int[] array) {
    if(array.length < 2)
      return array.length;

    int outsize=1; // first is always kept

    outerloop: for (int consider = 1; consider < array.length; ++consider) {

      for(int compare=0;compare<outsize;++compare)
        if(array[consider]==array[compare])
          continue outerloop; // already present; advance to next compare

      // if we get here, we know it's new so append it to output
      array[outsize++]=array[consider]; // could test first, not worth it. 
    }

    return outsize; // length is last written position plus 1
  }

  private static void printRemoveDupes(int[] array) {
    int newlength=removeDupes(array);
    System.out.println(Arrays.toString(Arrays.copyOfRange(array, 0, newlength)));
  }

  public static void main(final String[] args) {
    printRemoveDupes(new int[] { 3, 45, 1, 2, 3, 3, 3, 3, 2, 1, 45, 2, 10 });
    printRemoveDupes(new int[] { 2, 2, 3, 3 });
    printRemoveDupes(new int[] { 1, 1, 1, 1, 1, 1, 1, 1 });
  }
}

LATE ADDITION: Since folks expressed confusion about point 4 in my explanation, here’s the loop rewritten without labelled continue:

for (int consider = 1; consider < array.length; ++consider) {
  boolean matchfound=false;

  for(int compare=0;compare<outsize;++compare) {
    if(array[consider]==array[compare]) {
      matchfound=true;
      break;
    }

    if(!matchFound) // only add it to the output if not found
      array[outsize++]=array[consider];
}

Hope that helps. Labelled continue is a rarely-used feature of Java, so it isn’t too surprising that some folks haven’t seen it before. It’s useful, but it does make code harder to read; I probably wouldn’t use it in anything much more complicated than this simple algorithm.

Accepted Answer