4
\$\begingroup\$

Is there a simpler way to implement this function?

function has_duplicates(arr) {
  var myObject = {};

  for (var key in arr) {
    if (myObject[arr[key]])
      return true;
    else
      myObject[arr[key]] = true;
  }
  return false;
}

console.log(has_duplicates(["foo", "bar", "baz", "quux", "foo"]));
\$\endgroup\$
6
\$\begingroup\$
function has_duplicates(arr) {

In JS, function names are usually in camelCase. So this should be hasDuplicates.

for (var key in arr) {

Don't use for-in with arrays. for-in loops will run through properties, including prototype properties. Use a regular for loop with counters. A forEach would also work, but you can't bail out in the middle of the array.

So far, iirc, a loop and hash is favorable in this scenario since it's just O(n) and you can bail out in the middle of the operation.


Another way to do it is the following. The concept is that when a value appears twice, indexOf and lastIndexOf will not be the same, thus adding the entry to the array created by filter.

function hasDuplicates(arr){
  return !!arr.filter(fuction(value){
    return arr.indexOf(value) !== arr.lastIndexOf(value);
  }).length;
}

Another way to do it is by using ES6's Set. The concept is that sets only hold unique values. When you try to add a duplicate, it won't be added to the set. If there is a mismatch in the array length and set size, you jumped over a duplicate somewhere, thus revealing the existence of the duplicate.

function hasDuplicates(arr){
  var set = new Set();
  arr.forEach(function(value){ set.add(value); });
  return set.size !== arr.length;
}

Going with @PeterCordes's suggestion, you can use Set and check on each iteration the size mismatch. We can assume false until a mismatch happens.

function hasDuplicates(arr){
  var set = new Set();
  for(var i = 0; i < arr.length; i++){
    set.add(arr[i]);
    if(set.size !== i + 1) return true;
  }
  return false;
}
\$\endgroup\$
  • \$\begingroup\$ Yes, use a hash-based Set to get an O(n) duplicate check. Checking indexOf == lastIndexOf is not great: if there are repeats between element 5 and element 10, for example, you're still scanning the entire array for elements 0 to 4. You're repeating even more work than is needed with an O(n^2) time solution that doesn't use any temporary storage. A very similar question came up on SO, where I went into detail about different ways to use indexOf: stackoverflow.com/a/32523601/224132. \$\endgroup\$ – Peter Cordes Sep 18 '15 at 2:50
  • \$\begingroup\$ @PeterCordes Yeah. Hash is better. But if performance isn't a concern, readability and maintainability is always the next in line. Who wouldn't want a 3-liner duplicate detection? :D \$\endgroup\$ – Joseph Sep 18 '15 at 12:09
  • 1
    \$\begingroup\$ I was talking about the 3-line implementation using ES6's Set, which the docs say must use a hash table under the hood, or something else that is at least sub-linear time per insert / lookup (so a binary tree of some sort is allowed, but not linear searches). people.mozilla.org/~jorendorff/es6-draft.html#sec-set-objects. Also, if you expect to find a duplicate early in a long list, check set.size after every add. (This is probably faster than checking membership and then adding, which probably hashes the input twice.) \$\endgroup\$ – Peter Cordes Sep 18 '15 at 14:34
  • 1
    \$\begingroup\$ That last code example you added does not work. set.size increases as the loop continues, but arr.length remains the same throughout the loop. \$\endgroup\$ – gilly3 Sep 18 '15 at 20:34
3
\$\begingroup\$

Don't use for..in to iterate an array, because for..in is for enumerating objects and will enumerate over properties, including prototype properties. To iterate, use a normal for loop with a counter.

ES5

ES5 introduced some array iteration methods. Array.some() is the logical choice for this case, since it terminates the loop as soon as you've found an element that matches your condition.

function hasDuplicates(arr) {
  var valueHash = {};
  return arr.some(function(item) {
    var exists = valueHash[item];
    valueHash[item] = true;
    return exists;
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

ES6

If you can use ES6, you have the new Set object available, which is optimized for this kind of work. The constructor takes an iterable (such as an array) as an argument. So, you can just create a Set, and compare it's size to the array's length:

function hasDuplicates(arr) {
  return new Set(arr).size < arr.length;
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

Now, I don't know, but it's conceivable that this could be slow on a large array. If your array is large, and there could be many duplicates, it might be faster to loop through and add items to the Set one at a time. Use the JS5 function from above, but use a Set instead of an Object:

function hasDuplicates(arr){
  var set = new Set();
  return arr.some(function(item) {
    var exists = set.has(item);
    set.add(item);
    return exists;
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

It has been suggested that checking Set.has() followed by Set.add() could require the hash being computed twice, and thus be slower. If that's the case, it may perform better by checking Set.size instead of using Set.has().

function hasDuplicates(arr){
  var set = new Set();
  return arr.some(function(item, i) {
    return set.add(item).size == i; // while the array is distinct, set.size is i + 1
  });
}

document.write(hasDuplicates(["foo", "bar", "baz", "quux", "foo"]));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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