5
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – jfriend00 May 24 '14 at 3:12
  • \$\begingroup\$ 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 \$\endgroup\$ – megawac May 24 '14 at 3:35
  • \$\begingroup\$ 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. \$\endgroup\$ – 200_success May 26 '14 at 21:02
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – David Knipe May 26 '14 at 22:15
  • \$\begingroup\$ 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. \$\endgroup\$ – PAEz May 27 '14 at 22:32
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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}. \$\endgroup\$ – David Knipe May 26 '14 at 22:10
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ As far as I know, array.indexOf is a O(n) operation so this solution is O(n^2). \$\endgroup\$ – styfle May 26 '14 at 20:54

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.