Comparing two arrays in Javascript - Returning differences

Question

Assuming we have:

array1 = ['A', 'B', 'C', 'D', 'E']; array2 = ['C', 'E'];

Is there a proven and fast solution to compare two arrays against each other, returning one array without the values appearing in both arrays (C and E here). So:

array3 = ['A', 'B', 'D']

should be the output of the solution. (jquery may be involved)

thx.

Answer 1

This is a set difference. A simple implementation is:

jQuery.grep(array1, function(el)
                    {
                        return jQuery.inArray(el, array2) == -1;
                    });

This is O(m * n), where those are the sizes of the arrays. You can do it in O(m + n), but you need to use some kind of hash set. You can use a JavaScript object as a simple hash set for strings. For relatively small arrays, the above should be fine.

Answer 2

a proven fast solution that i know of is a binary search that you can use after you sort one of the arrays. so the solution takes time that depends on the sorting algorithm. but is at least log(N).

Answer 3

I accepted Matthews Solution, but dont want to ignore a different faster solution i just found.

 var list1 = [1, 2, 3, 4, 5, 6];
 var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
 var lookup = {};

 for (var j in list2) {
      lookup[list2[j]] = list2[j];
  }

  for (var i in list1) {
      if (typeof lookup[list1[i]] != 'undefined') {
          alert('found ' + list1[i] + ' in both lists');
          break;
 } 
 }

Source: Optimize Loops to Compare Two Arrays