Checking for Duplicates in a JavaScript Array

JavaScript has an in operator, that allows us to look through an object to see if we can find a property. If we create an object containing particular items in an array, we can then look through those items to see if we find a match.

Using prototypes, we can easily create a new method that will apply to all arrays. Let’s look at this in pieces.

The first thing we want to do is attach a method to the array prototype.

Array.prototype.containsDuplicates = function() {};

We can now do something like:

var dupesFound = [1,2,3].containsDuplicates();

…although this will won’t yet return anything, of course.

The next thing we’ll want to do, is loop through the contents of our array. For each item we will need to create an array with every item except our current one to check against (otherwise we will match against our current item, and always find a match).

In my previous post on iterating through arrays we already know the fastest way to iterate through an array (assuming we don’t mind doing it in reverse) so we’ll do that, and for each iteration create a new array containing all but the current item using the slice() and concat() methods.

var i=this.length;
var a;
while (i--) {
	a = this.slice(0,i).concat(this.slice(i+1,this.length));
}

Next, we’ll create an object and loop through our new array, creating an empty property of the object for each item in the array.

o = {};
j = a.length;
while (j--) {
	o[a[j]] = '';
}

Finally, we can now check this object for our current item, and return true if we found a match.

if (this[i] in o) {
	return true;
}

So, putting it all together (remembering to return false if we don’t find a match:

Array.prototype.containsDuplicates = function() {
	var i=this.length;
	var a, o, j;
	while (i--) {
		a = this.slice(0,i).concat(this.slice(i+1,this.length));
                o = {};
                j = a.length;
                while (j--) {
                    o[a[j]] = '';
                }
		if (this[i] in o) {
			return true;
		}
	}
	return false;
};

I generally don’t advocate modifying the base prototypes in JavaScript – it can cause all sorts of problems later on, so here’s the same methodology as a function.

var containsDuplicates = function(a) {
	var i=a.length;
	var a2, o, j;
	while (i--) {
		a2 = a.slice(0,i).concat(a.slice(i+1,a.length));
                o = {};
                j = a2.length;
                while (j--) {
                    o[a2[j]] = '';
                }
		if (a[i] in o) {
			return true;
		}
	}
	return false;
};

I hope this helps someone. Feel free to suggest ways to make this more efficient.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>