JavaScript: Best Way to return true if found values repeated in an array

Question

Possible Duplicate:
Easiest way to find duplicate values in a JavaScript array

Let's say I have an array with thousands of elements and

I want to return true if there are 2 or more elements with the same value.

I know I can run a for loop and do a check on every pair of elements to find the answer.

But is there a faster way? And what's the best way?

score 1 · Answer 1 · answered Jun 05 '12 at 14:25

1

Sort it (whatever the comparator) and then scan. O(n log(n)).

answered Jun 05 '12 at 14:25

Alexander Pavlov

31,598
5
67
93

This problem has a O(n) solution, see my answer – Samuel Rossille Jun 05 '12 at 14:31
Sure it has, but requires O(n) memory (and with _"thousands of elements"_ this might or might not be a considerable impact.) – Alexander Pavlov Jun 05 '12 at 14:33

Oleksi · Accepted Answer · 2012-06-05T14:34:20.300

1

This is basically the Element Distinctness Problem. You can read about it, but with only 1000 elements, the optimizations are probably not worth it.

If you really want to optimize it, you can push the elements into a hash table and check if collisions are duplicates. This will give you O(n) on average (amortized), but O(n^2) in worst case.

edited Jun 05 '12 at 14:34

answered Jun 05 '12 at 14:26

Oleksi

12,947
4
56
80

score 0 · Answer 3 · answered Jun 05 '12 at 14:26

0

Probably the fastest way would be to use the native methods. inArray is not one of them. You could use indexOf and default to a for loop if that method doens't exists (older browsers).

answered Jun 05 '12 at 14:26

Deleteman

8,500
6
25
39

Samuel Rossille · Answer 4 · 2012-06-05T14:38:30.520

0

There is a faster way. It's concrete implementation depends on what you have in the array. But the idea is the pseudo code below:

let's say you have an id(element) function that returns a string identifier of your element.

var map = {};

for(var i = 0; i < myArray.length; i++) {
    var currentId = id(myArray[i]);
    if(map.hasOwnProperty(id)) return true;
    map[id] = true;
}

The complexity here is linear.

If you don't have a natural id, you can either build one from the properties which identify the object, or do something smarter... the smartest thing you can do here is reimplementing a hashmap.

edited Jun 05 '12 at 14:38

answered Jun 05 '12 at 14:27

Samuel Rossille

18,940
18
62
90

1

This is linear on average, but in the presence of hash collisions, this might deteriorate to quadratic. – Oleksi Jun 05 '12 at 14:33
@AlexanderPavlov that was stupid, tx – Samuel Rossille Jun 05 '12 at 14:40
@Oleksi id here is not a hash. Do you mean that the native javascript hashmap's performance may degrade to quadratic in some cases ? If so, what can we say about the worse case complexity of the sort... ? – Samuel Rossille Jun 05 '12 at 14:41

score 0 · Answer 5 · answered Jun 05 '12 at 14:31

Try this:

Array.prototype.elementsNotDistinct = function () {
    var i, j, length = this.length - 1;

    for(i = 0; i < length; i++)
        for (j = i + 1; j <= length; j++)
            if (this[i] === this[j]) return true;

    return false;
};

Then if you have an array called a all you need to do is:

if (a.elementsNotDistinct()) {
    // do something
}

score 0 · Answer 6 · answered Jun 05 '12 at 14:33

I think Array's built in indexOf operation will work brilliantly for you (depending on the data you need to sort )

// Filter out all instances that occur twice or more.

var example = [ 1, 2, 3, 3, 3, 5, 4, 3, 5, 3 ];
var result = Array.filter( function ( element ) {
    return this.indexOf( element ) >= 2;
}  
// result is an array of [3,5]

return result.length === 0;

Fabrizio Calderan · Answer 7 · 2012-06-05T14:39:51.020

0

You could traverse the array and set an object key equal to the element found in the array (converted in a string). If your key already exists then you have found two element into the array with a duplicated value

function isAllDistinct() {
    var elements  = { },
        yourarray = [...];

    for (i=0, l=yourarray.length; i < l; i++) {
       var key = yourarray[i] + '';  // alternative to yourarray[i].toString()
       if (!elements[key]) {
         elements[key] = 1;
       }
       else {
         return false;
       }
    }
    return true;
}

Complexity : O(n)

edited Jun 05 '12 at 14:39

answered Jun 05 '12 at 14:33

Fabrizio Calderan

120,726
26
164
177

Most of the time, `yourarray[i] + ""` evaluates to `[object Object]` :) – Alexander Pavlov Jun 05 '12 at 14:37
well if a such case is verified then `toString()` will make the job – Fabrizio Calderan Jun 05 '12 at 14:39
Yes, this solution needs `toString()` implemented for all the objects in the array. – Alexander Pavlov Jun 05 '12 at 14:42

JavaScript: Best Way to return true if found values repeated in an array

7 Answers7