24
\$\begingroup\$
Array.prototype.unique = function() {
    var a = [], // uniques get placed into here
        b = 0; // counter to test if value is already in array 'a'

    for ( i = 0; i < this.length; i++ ) {
        var current = this[i]; // get a value from the original array

        for ( j = 0; j < a.length; j++ ) { // loop and check if value is in new array 
            if ( current != a[j] ) {
                b++; // if its not in the new array increase counter
            }
        }

        if ( b == a.length ) { // if the counter increased on all values 
                               // then its not in the new array yet
            a.push( current ); // put it in
        }

        b = 0; // reset counter
    }

    this.length = 0; // after new array is finished creating delete the original array
    for ( i = 0; i < a.length; i++ ) {
        this.push( a[i] ); // push all the new values into the original
    }

    return this; // return this to allow method chaining
}

I'm expecting this to be a slow checker especially because there is no sorting first. I'm interested in improving my sorting abilities etc so I thought I would get an early review.

\$\endgroup\$
  • 1
    \$\begingroup\$ Related to How can I quickly find unique list items? \$\endgroup\$ – megawac Aug 15 '14 at 17:56
  • \$\begingroup\$ One line implementation using ES6: Array.prototype.unique = function() { return [...new Set(this)]; } Test: [1,3,4,4,4,3,1,2,5,6,6,7].unique() // [1, 3, 4, 2, 5, 6, 7] \$\endgroup\$ – tanguy_k Sep 14 '17 at 23:45
21
\$\begingroup\$

You can use the indexOf function to check if a value exists in an array. This would simplify your code greatly:

Array.prototype.unique = function() {
    var a = [];
    for ( i = 0; i < this.length; i++ ) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }

    this.length = 0;
    for ( i = 0; i < a.length; i++ ) {
        this.push( a[i] );
    }

    return this;
}

At the end you are replacing the array's content. It would be better to not mutate the original array, but to return the new array instead with unique elements:

Array.prototype.unique = function() {
    var a = [];
    for ( i = 0; i < this.length; i++ ) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }
    return a;
}

The name a is a very poor choice. unique would have been better.

You should declare the loop variable i using let, to limit its scope to the current block, so the code becomes:

Array.prototype.unique = function() {
    var unique = [];
    for (let i = 0; i < this.length; i++) {
        let current = this[i];
        if (unique.indexOf(current) < 0) unique.push(current);
    }
    return unique;
}

Finally, there is a much more elegant solution to this problem, using the reduce function:

Array.prototype.unique = function() {
    return this.reduce(function(accum, current) {
        if (accum.indexOf(current) < 0) {
            accum.push(current);
        }
        return accum;
    }, []);
}

UPDATE (to answer your follow-up question)

If you want the function to take a parameter to decide whether it should modify the original array, you could try something like this:

Array.prototype.unique = function(mutate) {
    var unique = this.reduce(function(accum, current) {
        if (accum.indexOf(current) < 0) {
            accum.push(current);
        }
        return accum;
    }, []);
    if (mutate) {
        this.length = 0;
        for (let i = 0; i < unique.length; ++i) {
            this.push(unique[i]);
        }
        return this;
    }
    return unique;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ I did a small research and noticed that almost every Javascript Array function will never alter the original array... I think it's more coherent if you don't touch the original array. \$\endgroup\$ – Marco Acierno Aug 15 '14 at 14:51
  • \$\begingroup\$ I would agree if I didn't work alone and wasn't 100% sure no one else would ever use my implementation of this. So I think it will be fine. :D \$\endgroup\$ – eddie Aug 15 '14 at 15:34
  • 1
    \$\begingroup\$ Good answer. Your reduce could be changed to a filter, as that's basically what it is doing. \$\endgroup\$ – elclanrs Aug 15 '14 at 18:37
  • 2
    \$\begingroup\$ @MarcoAcierno: Off the top of my head, at least Array.pop(), Array.splice(), and Array.unshift() alter the original array. \$\endgroup\$ – hippietrail Jun 18 '16 at 6:28
11
\$\begingroup\$

In the case where there are a few duplicates, your algorithm has \$\mathcal{O}(n^2)\$ runtime.

If Javascript would have a widely available Set

Which it unfortunately does not yet have then one could do a really fast implementation like this:

Array.prototype.unique = function() {
    return [...(new Set(this))];
}

This would have been \$\mathcal{O}(n\cdot \log (n))\$ for a binary tree implementation or \$\mathcal{O}(n)\$ for a hash-based implementation.

Sorting and ditching order

If you sort the array first (as you suggested), you can then iterate over the array and copy the first element and then any remaining elements that differ from the previous element. This algorithm will have \$\mathcal{O}(n\cdot \log (n))\$ runtime. The sorting dominates the run-time here. For small lists, the code by Janos is adequate. If you want performance for large lists you really do need the sort.

This solution will not preserve order of elements but will have faster run time for larger lists:

Array.prototype.unique = function() {
    var sorted = this;
    sorted.sort();
    return sorted.filter(function(value, index, arr){
        if(index < 1) 
            return true;
        else
            return value != arr[index-1];
    });
}
\$\endgroup\$
  • \$\begingroup\$ If you use Set, you don't need the for at all. The MDN page says that if you pass to the constructor an iterator object they will be added so var seen = new Set(this); should be OK since a Set will not add duplicate items \$\endgroup\$ – Marco Acierno Aug 15 '14 at 14:54
  • \$\begingroup\$ Oh I didn't even notice that set preserves insertion order. I'm so used to that not being the case for Java and C++. Good catch! I can't test as I don't have time or a compatible browser right now but that should work according to the example on the MDN site. \$\endgroup\$ – Emily L. Aug 15 '14 at 14:57
  • \$\begingroup\$ It don't work in Google Chrome Canary, but in Firefox it works OK. Just remove the uneval (it creates a String) part, [...mySet] creates an Array from the Set. (i.imgur.com/GuwtZnT.png). It will take a lot of time before we can use it every day, but it's nice to see this in Javascript. (well, it's still a bad language.) \$\endgroup\$ – Marco Acierno Aug 15 '14 at 15:14
2
\$\begingroup\$

Here's an approach that utilises the fact that an object can also be used as a hashmap. The value of a is not used for any thing else than determine uniqueness

Array.prototype.unique = function() {
    var existing = {}, result = [], current;
    for ( i = 0; i < this.length; i++) {
        current = this[i];
        if(!existing.hasOwnProperty(current)) { 
           result.push(current);
           existing[current] = true; //any value will do
        }
    }
    return result;
}

This works in \$\mathcal{O}(n)\$ since it makes it possible to create the resulting array, while iterating over the original array. An algorithm based on sorting would likely have \$\mathcal{O}(n\cdot \log (n))\$.

That however doesn't necessarily mean that this implementation is faster, since the cost of inserting a value into the "hash" might be high enough, for some n to make this implementation slower. The strength lies in the simplicity

\$\endgroup\$

protected by Community Apr 26 '17 at 14:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.