Simplest code for array intersection in javascript

Simplest code for array intersection in javascript

What’s the simplest, library-free code for implementing array intersections in javascript? I want to write
intersection([1,2,3], [2,3,4,5])

and get
[2, 3]

Solutions/Answers:

Solution 1:

Use a combination of Array.prototype.filter and Array.prototype.indexOf:

array1.filter(value => -1 !== array2.indexOf(value))

Or as vrugtehagel suggested in the comments, you can use the more recent Array.prototype.includes for even simpler code:

array1.filter(value => array2.includes(value))

For older browsers:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

Solution 2:

Destructive seems simplest, especially if we can assume the input is sorted:

/* destructively finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *  State of input arrays is undefined when
 *  the function returns.  They should be 
 *  (prolly) be dumped.
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b)
{
  var result = [];
  while( a.length > 0 && b.length > 0 )
  {  
     if      (a[0] < b[0] ){ a.shift(); }
     else if (a[0] > b[0] ){ b.shift(); }
     else /* they're equal */
     {
       result.push(a.shift());
       b.shift();
     }
  }

  return result;
}

Non-destructive has to be a hair more complicated, since we’ve got to track indices:

/* finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length(), b.length())
 */
function intersect_safe(a, b)
{
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
}

Solution 3:

If your environment supports ECMAScript 6 Set, one simple and supposedly efficient (see specification link) way:

function intersect(a, b) {
  var setA = new Set(a);
  var setB = new Set(b);
  var intersection = new Set([...setA].filter(x => setB.has(x)));
  return Array.from(intersection);
}

Shorter, but less readable (also without creating the additional intersection Set):

function intersect(a, b) {
      return [...new Set(a)].filter(x => new Set(b).has(x));
}

Avoiding a new Set from b every time:

function intersect(a, b) {
      var setB = new Set(b);
      return [...new Set(a)].filter(x => setB.has(x));
}

Note that when using sets you will only get distinct values, thus new Set[1,2,3,3].size evaluates to 3.

Solution 4:

Using Underscore.js or lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]

Solution 5:

My contribution in ES6 terms. In general it finds the intersection of an array with indefinite number of arrays provided as arguments.

Array.prototype.intersect = function(...a) {
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
     arr = [0,1,2,3,4,5,6,7,8,9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Solution 6:

How about just using associative arrays?

function intersect(a, b) {
    var d1 = {};
    var d2 = {};
    var results = [];
    for (var i = 0; i < a.length; i++) {
        d1[a[i]] = true;
    }
    for (var j = 0; j < b.length; j++) {
        d2[b[j]] = true;
    }
    for (var k in d1) {
        if (d2[k]) 
            results.push(k);
    }
    return results;
}

edit:

// new version
function intersect(a, b) {
    var d = {};
    var results = [];
    for (var i = 0; i < b.length; i++) {
        d[b[i]] = true;
    }
    for (var j = 0; j < a.length; j++) {
        if (d[a[j]]) 
            results.push(a[j]);
    }
    return results;
}