JavaScript Array Comparison (aka Set Comparison)

Question

I want to compare the values in two arrays. The order of the values doesn't matter. Basically they are two Sets. This function returns true if the values are the same in both arrays, or false otherwise.

function compareSets(a1, a2) {
 if (a1.length !== a2.length) {
 return false;
 }
 var len = a1.length;
 var a1Set = {};
 // Convert a1 into a Set
 for (var i = 0; i < len; i++) {
 var value1 = a1[i];
 a1Set[value1] = true;
 }
 // Compare a2 values to a1 values
 for (var i = 0; i < len; i++) {
 var value2 = a2[i];
 if (!(value2 in a1Set)) {
 return false;
 }
 }
 return true;
}

This is an \$O(n)\$ solution which is better than the naive \$O(n^2)\$. I think it is always safe to say that if the lengths are different, the arrays are not the same.

Is there any way I can make this more concise?

• jfriend00: You could use actual set functionality like here which has an .equals() and .diff() method and others for comparing two sets. More info here in this stackoverflow answer.
• megawac: a1Set[value1] = true; this solution is less correct than the naive? solution of storing values in an array and using index of as it won't work for non primitives (e.g. try comparing [{1: 'a', 2: 'b'}] with [{}] as you're storing the string representation of the object
• 200_success: We generally don't allow code in questions to be edited in a way that invalidates existing answers. (The more appropriate action would have been to tag the question as typescript instead.) Normally, I'd revert such edits, but I'll let this one slide.
• David Knipe: What if the arrays have repeated elements? With your function, ['a', 'a', 'b'] would be considered equal to ['a', 'b', 'b'], but not equal to ['a', 'b']. Also, letting var x = ['a', 'a'], y = ['a', 'b'];, we get compareSets(x, y) == false but compareSets(y, x) == true.
• PAEz: This aint concise and dont think its O(n) or woteva that is, I just wanted to see if I could make one that actually works ;).... jsbin.com/coweb/1/edit ...tried to take into account what @200_success said as well.

Answer 1

In JavaScript objects, keys are always strings, or converted into strings. Therefore, all the elements of a1 and a2 will be compared as if they were stringified. For example, compareSets(['true'], [true]) returns true. I consider that to be unexpected behaviour that either needs to be fixed or documented.

• David Knipe: Furthermore, you have to be careful about the order of keys in an object. For example, {x:1,y:2} is equivalent to {y:2,x:1}.

Answer 2

You can use one loop and compare each other on each iteration. You can use indexOf to check for one value on the other.

function compareSets(a1, a2) {
 //length check (you said it was safe to assume different lengths is not the same set)
 if (a1.length !== a2.length) return false;
 // Contents check
 var len = a1.length;
 while(len--){
 // If value at index doesn't exist in the other
 // indexOf returns -1 for a non-existent value and !~ turns -1 to true
 // If either one returns a -1 anywhere in the routine, break away immediately
 if(!~a2.indexOf(a1[len]) || !~a1.indexOf(a2[len])){
 return false;
 }
 }
 // All exist with each other, return true
 return true;
}

• styfle: As far as I know, array.indexOf is a O(n) operation so this solution is O(n^2).