Find and show duplicated value

Question

Any idea how to get this:

var MyArr = [0,1,2,3,"something",44,661,3,1,"something"]
var Results = [1,3,"something"]

I just want to find duplicated values in my array.

@Daniel, technically this duplicates another question, but that question has a defective accepted answer (does not properly deal with triplicates), and there are several answers that have mis-interpreted the question (and provided algorithms for determining uniques). — brainjam, Sep 24 '13 at 20:19

score 2 · Accepted Answer · answered Sep 24 '13 at 13:42

2

Use a for loop:

var Results = [];
MyArr.forEach(function(el, idx){
    //check if value is duplicated
    var duplicated = MyArr.indexOf(el, idx + 1) > 0;
    if(duplicated && Results.indexOf(el) < 0) {
        //duplicated and not in array
        Results.push(el);
    }
});

answered Sep 24 '13 at 13:42

Naftali

144,921
39
244
303

No problem ^_^ Happy to help @maniootek – Naftali Sep 24 '13 at 13:49
Isn't this an O(n2) solution? – Manu Manjunath Sep 24 '13 at 14:22
It's an O(n^2) solution, obviously. – Sukhanov Niсkolay Sep 24 '13 at 14:28

Sukhanov Niсkolay · Answer 2 · 2013-09-24T14:27:36.820

Solution with O(n) time and O(n) space. Example:

Results = duplicates(MyArr);

Using map data structure. Works only if there are strings or numbers in MyArr;

function duplicates(input) {

    var results = [],
        _map = {};

    for (var i in input) {

        if (typeof _map[input[i]] == "undefined") {

            _map[input[i]] = 1;
        } 
        else {

            _map[input[i]]++;
        }
    }

    for (var argument in _map) {

        if (_map[argument] > 1) {

            results.push(argument);
        }
    }

    return results;
}

PS: Because _map[input[i]] takes O(1) time because it is a hash table, but indexOf() takes O(n) time. PS2: Another solution with lower constant:

function duplicates(input) {

    var results = [],
        _map = {};
        WAS = 1,
        SKIP = -1;

    for (var i in input) {

        if (typeof _map[input[i]] == "undefined") {

            _map[input[i]] = WAS;
        } 
        else if (_map[input[i]] == WAS) {

            _map[input[i]] = SKIP;
            results.push(input[i]);
        } 
    }

    return results;
}

score 0 · Answer 3 · answered Sep 24 '13 at 13:54

0

You could store each value in a new array, and before adding a new item to such array check if it already exists, and get the results back. Example using Array.forEach():

var myArr  = [1,2,3,2];
var results = [];

myArr.forEach(function(item) {
  if (results.indexOf(item) < 0) {
     results.push(item);
  }
});

If you just want the duplicated values, you could use a very similar approach and make use of Array.filter.

Note: beware that Array.indexOf() does not work on IE8, for example, you could use jQuery.inArray() method

answered Sep 24 '13 at 13:54

lmerino

173
2
11

This will get **all** values (including ones which are not duplicate) – Naftali Sep 24 '13 at 13:55
Why add jQuery? [Make your own `.indexOf`](http://stackoverflow.com/a/9768663/561731) – Naftali Sep 24 '13 at 13:56
"This will get all values (including ones which are not duplicate)" Eh...? Well, your version is a bit faster since you indicate the index anyways. – lmerino Sep 24 '13 at 13:57

score 0 · Answer 4 · answered Sep 24 '13 at 14:33

You can mimic a counted set by using an object whose properties are elements of the set and whose values are the number of occurrences. So you can convert your array to a counted set and read off the elements that have a count of two or more. (This works only if the elements of MyArr are strings or numbers.)

So try this:

var counts = {} ;
MyArr.forEach(function(el){
    counts[el] = counts[el]==undefined ? 1 : counts[el]+1 ;
});
var Results = Object.keys(counts).filter(function(el){
    return counts[el] > 1 ;
}) ;

Find and show duplicated value

4 Answers4