1

I need to know if one or more duplicates exist in a list. Is there a way to do this without travelling through the list more than once?

Thanks guys for the suggestions. I ended up using this because it was the simplest to implement:

var names = [];
var namesLen = names.length;
for (i=0; i<namesLen; i++) {
    for (x=0; x<namesLen; x++) {
        if (names[i] === names[x] && (i !== x)) {alert('dupe')}
    }
}
kht
  • 317
  • 1
  • 4
  • 14
  • A list of what? strings, ints, etc ... – JaredPar Oct 28 '11 at 22:41
  • underscore's uniq method may be of interest to you. http://documentcloud.github.com/underscore/#uniq – Chris Biscardi Oct 28 '11 at 22:49
  • @JaredPar In this case, strings. – kht Oct 28 '11 at 22:51
  • Sounds like an interview question. – gilly3 Oct 28 '11 at 22:59
  • 1
    That is the most inefficient way to do it. Might be easiest but you are going through the list n^2 times. Add a few hundred items and it will choke. At least if you are going to be that inefficient prune out your duped items so you don't have multiple alerts on the same one and make x=i+1 to start your second loop so you don't compare the same items every single pass. That will get you closer to n*log(n) still bad but not as. – benjamin Oct 29 '11 at 03:37
  • Yup, going through the list n^2 times is the least efficient way, however I figured it was worth giving up speed for simplicity since it wont be used on a list of more than 30 strings. – kht Oct 29 '11 at 14:23
  • Well at least if you just make the easy change of x=i+1 you will eliminate a ton of repeat comparisons. Currently you are comparing names[1] to names[2]... Next time through you are comparing names[2] to names[1] which gives the same result. Making x always start greater than i will eliminate the double compares and if your list ever gets bigger than 30 it could lessen the headache in the future. Happy coding. – benjamin Oct 29 '11 at 17:58
  • Makes sense, I will implement that – kht Oct 30 '11 at 19:28

4 Answers4

3

Well the usual way to do that would be to put each item in a hashmap dictionary and you could check if it was already inserted. If your list is of objects they you would have to create your own hash function on the object as you would know what makes each one unique. Check out the answer to this question.

JavaScript Hashmap Equivalent

Community
  • 1
  • 1
benjamin
  • 1,087
  • 7
  • 10
3

This method uses an object as a lookup table to keep track of how many and which dups were found. It then returns an object with each dup and the dup count.

function findDups(list) {
    var uniques = {}, val;
    var dups = {};
    for (var i = 0, len = list.length; i < len; i++) {
        val = list[i];
        if (val in uniques) {
            uniques[val]++;
            dups[val] = uniques[val];
        } else {
            uniques[val] = 1;
        }
    }
    return(dups);
} 

var data = [1,2,3,4,5,2,3,2,6,8,9,9];
findDups(data);   // returns  {2: 3, 3: 2, 9: 2}

var data2 = [1,2,3,4,5,6,7,8,9];
findDups(data2);  // returns {} 

var data3 = [1,1,1,1,1,2,3,4];
findDups(data3);  // returns {1: 5}

Since we now have ES6 available with the built-in Map object, here's a version of findDups() that uses the Map object:

function findDups(list) {
    const uniques = new Set();     // set of items found
    const dups = new Map();        // count of items that have dups
    for (let val of list) {
        if (uniques.has(val)) {
            let cnt = dups.get(val) || 1;
            dups.set(val, ++cnt);
        } else {
            uniques.add(val);
        }
    }
    return dups;
} 

var data = [1,2,3,4,5,2,3,2,6,8,9,9];
log(findDups(data));   // returns  {2 => 3, 3 => 2, 9 => 2}

var data2 = [1,2,3,4,5,6,7,8,9];
log(findDups(data2));  // returns empty map 

var data3 = [1,1,1,1,1,2,3,4];
log(findDups(data3));  // returns {1 => 5}

// display resulting Map object (only used for debugging display in snippet)
function log(map) {
    let output = [];
    for (let [key, value] of map) {
        output.push(key + " => " + value);
    }
    let div = document.createElement("div");
    div.innerHTML = "{" + output.join(", ") + "}";
    document.body.appendChild(div);
}
jfriend00
  • 683,504
  • 96
  • 985
  • 979
  • Updated answer using ES6 constructs like `Set` and `Map`. This also allows `findDups()` to work for any type of array element including objects (not just things that have a unique auto string conversion). – jfriend00 May 25 '18 at 00:56
2

If your strings are in an array (A) you can use A.some- it will return true and quit as soon as it finds a duplicate, or return false if it has checked them all without any duplicates.

has_duplicates= A.some(function(itm){
    return A.indexOf(itm)===A.lastIndexOf(itm);
});
kennebec
  • 102,654
  • 32
  • 106
  • 127
0

If your list was just words or phrases, you could put them into an associative array.

var list=new Array("foo", "bar", "foobar", "foo", "bar");
var newlist= new Array();
for(i in list){
    if(newlist[list[i]])
        newlist[list[i]]++;
    else
        newlist[list[i]]=1;
}

Your final array should look like this: "foo"=>2, "bar"=>2, "foobar"=>1

Tim Withers
  • 12,072
  • 5
  • 43
  • 67