4

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)?

Improve this question
2
  • I actually think the code looks pretty good as written. It's hard to write in-place code that looks anywhere near as neat as solutions that work on immutable objects. Commented Sep 10, 2015 at 19:44
  • Thanks for your feedback. I'm pretty early in my course so they're drilling the basics/fundamentals as much as possible into us. My intuition hasn't developed to a point where I can look at something and know if it's an optimal solution on my own, so SO has been a great help Commented Sep 10, 2015 at 20:15

5 Answers 5

Reset to default
7

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think this solution is great, I'm going to accept this is as the answer
arr.length = k; is a nice touch crying for documentation.
1

This seems like a simpler solution to me:

function remove_dupes(arr){
  var seen = {};
  var dupes_removed = [];

  for( var i = 0; i < arr.length; i++) {
    if (!seen[arr[i]]) {
      dupes_removed.push(arr[i]);
      seen[arr[i]] = true;
    }
  }

  return dupes_removed;
}

This runs in somewhere between O(n) and O(nlogn) time (because JS hash lookups are between O(1) and O(logn) time). This also guarantees the result will be stable. The other solutions so far either run in O(n^2) or aren't stable.

Improve this answer

2 Comments

However, this solution isn't in place as the question requires. It creates a new array.
Yes, what @ivern said. I like the cleanliness of this code but for class we were asked not to create a new array. Could you modify your solution to do it in place as much as possible?
0

You can use indexOf to see if that value exists in arr than push to a new one

function remove_dupes(arr){
  var newArr = [];
  for( var i = 0; i < arr.length; i++){ 
    if(newArr.indexOf(arr[i]) === -1){
      newArr.push(arr[i]);
    }
  }
  
  return newArr;
}

var myArr = [2,4,2,4,6,6,6,2,2,1,10,33,3,4,4,4];

console.log(remove_dupes(myArr));

Improve this answer

1 Comment

Nice clean solution but I was challenged not to create an array to return and couldn't use functions like indexOf. I had to do it in place as much as possible
0

You can use Array.prototype.splice to change the array in place (fiddle - look at the console):

var arr = [1, 54, 5, 3, 1, 5, 20, 1, 54, 54];

var seen = {};

var length = arr.length;

var i = 0;

while (i < length) {
    if (seen[arr[i]] !== undefined) {
        arr.splice(i, 1);
        length--;
    } else {
        seen[arr[i]] = true;
    }

    i++;
}

console.log(arr);

This is O(n^2) as splice is O(n), and we iterate n elements.

Improve this answer

4 Comments

I had done something like this originally using splice but my instructor challenged me to not use any built in functions so I was forced to go a different route
No problems, just add it to the question.
I mentioned it in the last line of the question, but that should be more visible, you're right. I'll make the edit
No my bad. Definitely helps the question to be more clear about it upfront and keep all of the requirements in one place. Still learning my way around SO, appreciate the feedback
0

This is a compact solution I am using in my JS array subclass:

if ( !Array.unique )
{
    Array.prototype.unique = function()
    {
        var tmp = {}, out = [], _i, _n ;
        for( _i = 0, _n = this.length; _i < _n; ++_i )
        if(!tmp[this[_i]]) { tmp[this[_i]] = true; out.push(this[_i]); }
        return out;
    }
}
Improve this answer

6 Comments

This is creating a new array and returning it isn't it? As I'm reading it, this isn't doing it in place
Do you mean to 'use the same working array' with 'in place' ? Well, if so you might want to scan each element, check the array through .indexOf and, via .splice, remove the first indexed element each time .indexOf does not return -1 ... that's the basic idea, which has been already shown above
Correct. Same array. However, as stated in my question, I was not supposed to use any built in functions such as splice or indexOf. That was part of the challenege
Well, this sounds just like an exercise. Anyway, how to remove duplicates without "splicing" the array ?
The approach that I took (and the approach of the answer I accepted) is basically to move all unique elements to the front of the array, and move the duplicates to the end of the array. With a counter you know which index divides the uniques and dupes, so just truncate the array at that point.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.