Remove duplicates algorithm, in place and stable (javascript)

Question

In class today we were asked to write an algorithm.

Given an array, remove duplicate values:

• It should be stable, and shouldn't have to use an inner loop.
• Should be done in place, as best as possible
• No use of built in functions (I was only allowed to use .push)

After wrestling with it for a while, this is what I came up with.

function remove_dupes(arr){
  var seen = {};
  var count = 0;

  for( var i = 0; i < arr.length - count ; i++) {
    arr[i] = arr[i+count];

    if( seen[arr[i]] ) {
      count++;
      arr[i] = arr[i+count];
      i--;
    }

    seen[arr[i]] = true;
  }

  arr.length = arr.length - count;
}

Working JSBin

I have a bit of repeated code here and I feel that maybe the i-- isn't the best way to go.

Is there any way I could improve this code (without using built in functions)?

Answer 1

Finally, I think I got what you want without creating a new array:

function remove_dupes(arr){
  var seen = {};
  
  var k = 0;
  for( var i=0; i<arr.length ;i++) {
    if( !seen[arr[i]] ) {
      arr[k++] = arr[i];
      seen[arr[i]] = 'seen';
    }
  }
  
  arr.length = k;
}


var x = [ 1, 2, 1, 4, 5, 3, 'dojo', 4, 6, 6, 7, 7, 6, 7, 5, 6, 6, 6, 6, 7, 'dojo', 11 ];
remove_dupes(x);


document.write(x);

Hope it helps.