8

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.

Björn
  • 12,587
  • 12
  • 51
  • 70
  • Are the arrays both always sorted, as in your example? If so, this can be done in linear time by just walking the arrays. – Ben Zotto Aug 08 '10 at 03:25

3 Answers3

13

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

Björn
  • 12,587
  • 12
  • 51
  • 70
  • Particularly nice if one of the lists (here list2) needs to be compared to many candidates (many list1's). – JPM Jan 20 '13 at 20:42
  • 1
    on Chrome, the linked source reference is spotted as containing malware – superjos Jul 01 '13 at 15:49
12

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.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
  • Please consider updating this answer to use Array.prototype.filter instead of jQuery.grep since it'll provide a solution even if jQuery is not allowed. – Benjamin Gruenbaum Dec 13 '13 at 15:10
  • [Array.prototype.filter](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter) is indeed a no-library alternative. However, you need [Array.prototype.indexOf](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf) too (instead of inArray). However, both require loading a polyfill (provided at the links) in older browsers to achieve broad compatibility. Since the question allowed jQuery, I went with that since it has its own polyfill. – Matthew Flaschen Dec 17 '13 at 02:28
0

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).

akonsu
  • 28,824
  • 33
  • 119
  • 194