[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]

This question is related to javascript data-structures intersection

The answer is


function getIntersection(arr1, arr2){
    var result = [];
    arr1.forEach(function(elem){
        arr2.forEach(function(elem2){
            if(elem === elem2){
                result.push(elem);
            }
        });
    });
    return result;
}

getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]

I extended tarulen's answer to work with any number of arrays. It also should work with non-integer values.

function intersect() { 
    const last = arguments.length - 1;
    var seen={};
    var result=[];
    for (var i = 0; i < last; i++)   {
        for (var j = 0; j < arguments[i].length; j++)  {
            if (seen[arguments[i][j]])  {
                seen[arguments[i][j]] += 1;
            }
            else if (!i)    {
                seen[arguments[i][j]] = 1;
            }
        }
    }
    for (var i = 0; i < arguments[last].length; i++) {
        if ( seen[arguments[last][i]] === last)
            result.push(arguments[last][i]);
        }
    return result;
}

"filter" and "indexOf" aren't supported on Array in IE. How about this:

var array1 = [1, 2, 3];
var array2 = [2, 3, 4, 5];

var intersection = [];
for (i in array1) {
    for (j in array2) {
        if (array1[i] == array2[j]) intersection.push(array1[i]);
    }
}

Here's a very naive implementation I'm using. It's non-destructive and also makes sure not to duplicate entires.

Array.prototype.contains = function(elem) {
    return(this.indexOf(elem) > -1);
};

Array.prototype.intersect = function( array ) {
    // this is naive--could use some optimization
    var result = [];
    for ( var i = 0; i < this.length; i++ ) {
        if ( array.contains(this[i]) && !result.contains(this[i]) )
            result.push( this[i] );
    }
    return result;
}

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

_x000D_
_x000D_
Array.prototype.intersect = function(...a) {_x000D_
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));_x000D_
}_x000D_
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],_x000D_
     arr = [0,1,2,3,4,5,6,7,8,9];_x000D_
_x000D_
document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");
_x000D_
_x000D_
_x000D_


.reduce to build a map, and .filter to find the intersection. delete within the .filter allows us to treat the second array as though it's a unique set.

function intersection (a, b) {
  var seen = a.reduce(function (h, k) {
    h[k] = true;
    return h;
  }, {});

  return b.filter(function (k) {
    var exists = seen[k];
    delete seen[k];
    return exists;
  });
}

I find this approach pretty easy to reason about. It performs in constant time.


If your arrays are sorted, this should run in O(n), where n is min( a.length, b.length )

function intersect_1d( a, b ){
    var out=[], ai=0, bi=0, acurr, bcurr, last=Number.MIN_SAFE_INTEGER;
    while( ( acurr=a[ai] )!==undefined && ( bcurr=b[bi] )!==undefined ){
        if( acurr < bcurr){
            if( last===acurr ){
                out.push( acurr );
            }
            last=acurr;
            ai++;
        }
        else if( acurr > bcurr){
            if( last===bcurr ){
                out.push( bcurr );
            }
            last=bcurr;
            bi++;
        }
        else {
            out.push( acurr );
            last=acurr;
            ai++;
            bi++;
        }
    }
    return out;
}

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;
}

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;
}

function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
    for (j=0; j<B.length; j++) {
        if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
            result.push(A[i]);
        }
    }
}
return result;
}

A functional approach with ES2015

A functional approach must consider using only pure functions without side effects, each of which is only concerned with a single job.

These restrictions enhance the composability and reusability of the functions involved.

_x000D_
_x000D_
// small, reusable auxiliary functions_x000D_
_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
const apply = f => x => f(x);_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
  const zs = createSet(ys);_x000D_
  return filter(x => zs.has(x)_x000D_
     ? true_x000D_
     : false_x000D_
  ) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
_x000D_
_x000D_
// run it_x000D_
_x000D_
console.log( intersect(xs) (ys) );
_x000D_
_x000D_
_x000D_

Please note that the native Set type is used, which has an advantageous lookup performance.

Avoid duplicates

Obviously repeatedly occurring items from the first Array are preserved, while the second Array is de-duplicated. This may be or may be not the desired behavior. If you need a unique result just apply dedupe to the first argument:

_x000D_
_x000D_
// auxiliary functions_x000D_
_x000D_
const apply = f => x => f(x);_x000D_
const comp = f => g => x => f(g(x));_x000D_
const afrom = apply(Array.from);_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
  const zs = createSet(ys);_x000D_
  return filter(x => zs.has(x)_x000D_
     ? true_x000D_
     : false_x000D_
  ) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// de-duplication_x000D_
_x000D_
const dedupe = comp(afrom) (createSet);_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
_x000D_
_x000D_
// unique result_x000D_
_x000D_
console.log( intersect(dedupe(xs)) (ys) );
_x000D_
_x000D_
_x000D_

Compute the intersection of any number of Arrays

If you want to compute the intersection of an arbitrarily number of Arrays just compose intersect with foldl. Here is a convenience function:

_x000D_
_x000D_
// auxiliary functions_x000D_
_x000D_
const apply = f => x => f(x);_x000D_
const uncurry = f => (x, y) => f(x) (y);_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
  const zs = createSet(ys);_x000D_
  return filter(x => zs.has(x)_x000D_
     ? true_x000D_
     : false_x000D_
  ) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// intersection of an arbitrarily number of Arrays_x000D_
_x000D_
const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
const zs = [0,1,2,3,4,5,6];_x000D_
_x000D_
_x000D_
// run_x000D_
_x000D_
console.log( intersectn(xs, ys, zs) );
_x000D_
_x000D_
_x000D_


For simplicity:

// Usage
const intersection = allLists
  .reduce(intersect, allValues)
  .reduce(removeDuplicates, []);


// Implementation
const intersect = (intersection, list) =>
  intersection.filter(item =>
    list.some(x => x === item));

const removeDuplicates = (uniques, item) =>
  uniques.includes(item) ? uniques : uniques.concat(item);


// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];

const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];

// Example Usage
const intersection = allGroups
  .reduce(intersect, allPeople)
  .reduce(removeDuplicates, []);

intersection; // [jill]

Benefits:

  • dirt simple
  • data-centric
  • works for arbitrary number of lists
  • works for arbitrary lengths of lists
  • works for arbitrary types of values
  • works for arbitrary sort order
  • retains shape (order of first appearance in any array)
  • exits early where possible
  • memory safe, short of tampering with Function / Array prototypes

Drawbacks:

  • higher memory usage
  • higher CPU usage
  • requires an understanding of reduce
  • requires understanding of data flow

You wouldn't want to use this for 3D engine or kernel work, but if you have problems getting this to run in an event-based app, your design has bigger problems.


With some restrictions on your data, you can do it in linear time!

For positive integers: use an array mapping the values to a "seen/not seen" boolean.

function intersectIntegers(array1,array2) { 
   var seen=[],
       result=[];
   for (var i = 0; i < array1.length; i++) {
     seen[array1[i]] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if ( seen[array2[i]])
        result.push(array2[i]);
   }
   return result;
}

There is a similar technique for objects: take a dummy key, set it to "true" for each element in array1, then look for this key in elements of array2. Clean up when you're done.

function intersectObjects(array1,array2) { 
   var result=[];
   var key="tmpKey_intersect"
   for (var i = 0; i < array1.length; i++) {
     array1[i][key] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if (array2[i][key])
        result.push(array2[i]);
   }
   for (var i = 0; i < array1.length; i++) {
     delete array1[i][key];
   }
   return result;
}

Of course you need to be sure the key didn't appear before, otherwise you'll be destroying your data...


  1. Sort it
  2. check one by one from the index 0, create new array from that.

Something like this, Not tested well though.

function intersection(x,y){
 x.sort();y.sort();
 var i=j=0;ret=[];
 while(i<x.length && j<y.length){
  if(x[i]<y[j])i++;
  else if(y[j]<x[i])j++;
  else {
   ret.push(x[i]);
   i++,j++;
  }
 }
 return ret;
}

alert(intersection([1,2,3], [2,3,4,5]));

PS:The algorithm only intended for Numbers and Normal Strings, intersection of arbitary object arrays may not work.


Building on Anon's excellent answer, this one returns the intersection of two or more arrays.

function arrayIntersect(arrayOfArrays)
{        
    var arrayCopy = arrayOfArrays.slice(),
        baseArray = arrayCopy.pop();

    return baseArray.filter(function(item) {
        return arrayCopy.every(function(itemList) {
            return itemList.indexOf(item) !== -1;
        });
    });
}

This is probably the simplest one, besides list1.filter(n => list2.includes(n))

_x000D_
_x000D_
var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']_x000D_
var list2 = ['bread', 'cherry', 'ice cream', 'oats']_x000D_
_x000D_
function check_common(list1, list2){_x000D_
 _x000D_
 list3 = []_x000D_
 for (let i=0; i<list1.length; i++){_x000D_
  _x000D_
  for (let j=0; j<list2.length; j++){ _x000D_
   if (list1[i] === list2[j]){_x000D_
    list3.push(list1[i]);    _x000D_
   }  _x000D_
  }_x000D_
  _x000D_
 }_x000D_
 return list3_x000D_
 _x000D_
}_x000D_
_x000D_
check_common(list1, list2) // ["bread", "ice cream"]
_x000D_
_x000D_
_x000D_


intersection of N arrays in coffeescript

getIntersection: (arrays) ->
    if not arrays.length
        return []
    a1 = arrays[0]
    for a2 in arrays.slice(1)
        a = (val for val in a1 when val in a2)
        a1 = a
    return a1.unique()

Using jQuery:

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);

not about efficiency, but easy to follow, here is an example of unions and intersections of sets, it handles arrays of sets and sets of sets.

http://jsfiddle.net/zhulien/NF68T/

// process array [element, element...], if allow abort ignore the result
function processArray(arr_a, cb_a, blnAllowAbort_a)
{
    var arrResult = [];
    var blnAborted = false;
    var intI = 0;

    while ((intI < arr_a.length) && (blnAborted === false))
    {
        if (blnAllowAbort_a)
        {
            blnAborted = cb_a(arr_a[intI]);
        }
        else
        {
            arrResult[intI] = cb_a(arr_a[intI]);
        }
        intI++;
    }

    return arrResult;
}

// process array of operations [operation,arguments...]
function processOperations(arrOperations_a)
{
    var arrResult = [];
    var fnOperationE;

    for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++) 
    {
        var fnOperation = arrOperations_a[intI+0];
        var fnArgs = arrOperations_a[intI+1];
        if (fnArgs === undefined)
        {
            arrResult[intR] = fnOperation();
        }
        else
        {
            arrResult[intR] = fnOperation(fnArgs);
        }
    }

    return arrResult;
}

// return whether an element exists in an array
function find(arr_a, varElement_a)
{
    var blnResult = false;

    processArray(arr_a, function(varToMatch_a)
    {
        var blnAbort = false;

        if (varToMatch_a === varElement_a)
        {
            blnResult = true;
            blnAbort = true;
        }

        return blnAbort;
    }, true);

    return blnResult;
}

// return the union of all sets
function union(arr_a)
{
    var arrResult = [];
    var intI = 0;

    processArray(arr_a, function(arrSet_a)
    {
        processArray(arrSet_a, function(varElement_a)
        {
            // if the element doesn't exist in our result
            if (find(arrResult, varElement_a) === false)
            {
                // add it
                arrResult[intI] = varElement_a;
                intI++;
            }
        });
    });

    return arrResult;
}

// return the intersection of all sets
function intersection(arr_a)
{
    var arrResult = [];
    var intI = 0;

    // for each set
    processArray(arr_a, function(arrSet_a)
    {
        // every number is a candidate
        processArray(arrSet_a, function(varCandidate_a)
        {
            var blnCandidate = true;

            // for each set
            processArray(arr_a, function(arrSet_a)
            {
                // check that the candidate exists
                var blnFoundPart = find(arrSet_a, varCandidate_a);

                // if the candidate does not exist
                if (blnFoundPart === false)
                {
                    // no longer a candidate
                    blnCandidate = false;
                }
            });

            if (blnCandidate)
            {
                // if the candidate doesn't exist in our result
                if (find(arrResult, varCandidate_a) === false)
                {
                    // add it
                    arrResult[intI] = varCandidate_a;
                    intI++;
                }
            }
        });
    });

    return arrResult;
}

var strOutput = ''

var arrSet1 = [1,2,3];
var arrSet2 = [2,5,6];
var arrSet3 = [7,8,9,2];

// return the union of the sets
strOutput = union([arrSet1, arrSet2, arrSet3]);
alert(strOutput);

// return the intersection of 3 sets
strOutput = intersection([arrSet1, arrSet2, arrSet3]);
alert(strOutput);

// of 3 sets of sets, which set is the intersecting set
strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
alert(strOutput);

If you need to have it handle intersecting multiple arrays:

_x000D_
_x000D_
const intersect = (a1, a2, ...rest) => {
  const a12 = a1.filter(value => a2.includes(value))
  if (rest.length === 0) { return a12; }
  return intersect(a12, ...rest);
};

console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) 
_x000D_
_x000D_
_x000D_


I have written an intesection function which can even detect intersection of array of objects based on particular property of those objects.

For instance,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

and we want intersection based on the id property, then the output should be :

[{id: 20}]

As such, the function for the same (note: ES6 code) is :

const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
    const [fn1, fn2] = accessors;
    const set = new Set(arr2.map(v => fn2(v)));
    return arr1.filter(value => set.has(fn1(value)));
};

and you can call the function as:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

Also note: this function finds intersection considering the first array is the primary array and thus the intersection result will be that of the primary array.


Create an Object using one array and loop through the second array to check if the value exists as key.

function intersection(arr1, arr2) {
  var myObj = {};
  var myArr = [];
  for (var i = 0, len = arr1.length; i < len; i += 1) {
    if(myObj[arr1[i]]) {
      myObj[arr1[i]] += 1; 
    } else {
      myObj[arr1[i]] = 1;
    }
  }
  for (var j = 0, len = arr2.length; j < len; j += 1) {
    if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
      myArr.push(arr2[j]);
    }
  }
  return myArr;
}

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


This is a modern and simple ES6 way to do it that is also very flexible. It lets you specify multiple arrays as the arrays to compare the subject array to, and can work in both inclusive and exclusive mode.

// =======================================
// The function
// =======================================

function assoc(subjectArray, otherArrays, { mustBeInAll = true } = {}) {
  return subjectArray.filter((subjectItem) => {
    if (mustBeInAll) {
      return otherArrays.every((otherArray) =>
        otherArray.includes(subjectItem)
      );
    } else {
      return otherArrays.some((otherArray) => otherArray.includes(subjectItem));
    }
  });
}

// =======================================
// The usage
// =======================================

const cheeseList = ["stilton", "edam", "cheddar", "brie"];
const foodListCollection = [
  ["cakes", "ham", "stilton"],
  ["juice", "wine", "brie", "bread", "stilton"]
];

// Output will be: ['stilton', 'brie']
const inclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: false }),

// Output will be: ['stilton']
const exclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: true })

Live example: https://codesandbox.io/s/zealous-butterfly-h7dgf?fontsize=14&hidenavigation=1&theme=dark


Another indexed approach able to process any number of arrays at once:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = 0;
            index[v]++;
        };
    };
    var retv = [];
    for (var i in index) {
        if (index[i] == arrLength) retv.push(i);
    };
    return retv;
};

It works only for values that can be evaluated as strings and you should pass them as an array like:

intersect ([arr1, arr2, arr3...]);

...but it transparently accepts objects as parameter or as any of the elements to be intersected (always returning array of common values). Examples:

intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]

EDIT: I just noticed that this is, in a way, slightly buggy.

That is: I coded it thinking that input arrays cannot itself contain repetitions (as provided example doesn't).

But if input arrays happen to contain repetitions, that would produce wrong results. Example (using below implementation):

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]

Fortunately this is easy to fix by simply adding second level indexing. That is:

Change:

        if (index[v] === undefined) index[v] = 0;
        index[v]++;

by:

        if (index[v] === undefined) index[v] = {};
        index[v][i] = true; // Mark as present in i input.

...and:

         if (index[i] == arrLength) retv.push(i);

by:

         if (Object.keys(index[i]).length == arrLength) retv.push(i);

Complete example:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = {};
            index[v][i] = true; // Mark as present in i input.
        };
    };
    var retv = [];
    for (var i in index) {
        if (Object.keys(index[i]).length == arrLength) retv.push(i);
    };
    return retv;
};

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]

Hope this Helps for all versions.

function diffArray(arr1, arr2) {
  var newArr = [];

  var large = arr1.length>=arr2.length?arr1:arr2;
  var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1;
  for(var i=0;i<large.length;i++){
    var copyExists = false; 
    for(var j =0;j<small.length;j++){
      if(large[i]==small[j]){
        copyExists= true;
        break;
      }
    }
    if(!copyExists)
      {
        newArr.push(large[i]);
      }
  }

  for(var i=0;i<small.length;i++){
    var copyExists = false; 
    for(var j =0;j<large.length;j++){
      if(large[j]==small[i]){
        copyExists= true;
        break;
      }
    }
    if(!copyExists)
      {
        newArr.push(small[i]);
      }
  }


  return newArr;
}

Using Underscore.js or lodash.js

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

For arrays containing only strings or numbers you can do something with sorting, as per some of the other answers. For the general case of arrays of arbitrary objects I don't think you can avoid doing it the long way. The following will give you the intersection of any number of arrays provided as parameters to arrayIntersection:

var arrayContains = Array.prototype.indexOf ?
    function(arr, val) {
        return arr.indexOf(val) > -1;
    } :
    function(arr, val) {
        var i = arr.length;
        while (i--) {
            if (arr[i] === val) {
                return true;
            }
        }
        return false;
    };

function arrayIntersection() {
    var val, arrayCount, firstArray, i, j, intersection = [], missing;
    var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array

    // Search for common values
    firstArray = arrays.pop();
    if (firstArray) {
        j = firstArray.length;
        arrayCount = arrays.length;
        while (j--) {
            val = firstArray[j];
            missing = false;

            // Check val is present in each remaining array 
            i = arrayCount;
            while (!missing && i--) {
                if ( !arrayContains(arrays[i], val) ) {
                    missing = true;
                }
            }
            if (!missing) {
                intersection.push(val);
            }
        }
    }
    return intersection;
}

arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"]; 

I'll contribute with what has been working out best for me:

if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {

    var r = [], o = {}, l = this.length, i, v;
    for (i = 0; i < l; i++) {
        o[this[i]] = true;
    }
    l = arr1.length;
    for (i = 0; i < l; i++) {
        v = arr1[i];
        if (v in o) {
            r.push(v);
        }
    }
    return r;
};
}

Here is underscore.js implementation:

_.intersection = function(array) {
  if (array == null) return [];
  var result = [];
  var argsLength = arguments.length;
  for (var i = 0, length = array.length; i < length; i++) {
    var item = array[i];
    if (_.contains(result, item)) continue;
    for (var j = 1; j < argsLength; j++) {
      if (!_.contains(arguments[j], item)) break;
    }
    if (j === argsLength) result.push(item);
  }
  return result;
};

Source: http://underscorejs.org/docs/underscore.html#section-62


_x000D_
_x000D_
var arrays = [_x000D_
    [1, 2, 3],_x000D_
    [2, 3, 4, 5]_x000D_
]_x000D_
function commonValue (...arr) {_x000D_
    let res = arr[0].filter(function (x) {_x000D_
        return arr.every((y) => y.includes(x))_x000D_
    })_x000D_
    return res;_x000D_
}_x000D_
commonValue(...arrays);
_x000D_
_x000D_
_x000D_


A tiny tweak to the smallest one here (the filter/indexOf solution), namely creating an index of the values in one of the arrays using a JavaScript object, will reduce it from O(N*M) to "probably" linear time. source1 source2

function intersect(a, b) {
  var aa = {};
  a.forEach(function(v) { aa[v]=1; });
  return b.filter(function(v) { return v in aa; });
}

This isn't the very simplest solution (it's more code than filter+indexOf), nor is it the very fastest (probably slower by a constant factor than intersect_safe()), but seems like a pretty good balance. It is on the very simple side, while providing good performance, and it doesn't require pre-sorted inputs.


The performance of @atk's implementation for sorted arrays of primitives can be improved by using .pop rather than .shift.

function intersect(array1, array2) {
   var result = [];
   // Don't destroy the original arrays
   var a = array1.slice(0);
   var b = array2.slice(0);
   var aLast = a.length - 1;
   var bLast = b.length - 1;
   while (aLast >= 0 && bLast >= 0) {
      if (a[aLast] > b[bLast] ) {
         a.pop();
         aLast--;
      } else if (a[aLast] < b[bLast] ){
         b.pop();
         bLast--;
      } else /* they're equal */ {
         result.push(a.pop());
         b.pop();
         aLast--;
         bLast--;
      }
   }
   return result;
}

I created a benchmark using jsPerf: http://bit.ly/P9FrZK. It's about three times faster to use .pop.


function intersectionOfArrays(arr1, arr2) {
    return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}

_x000D_
_x000D_
// Return elements of array a that are also in b in linear time:_x000D_
function intersect(a, b) {_x000D_
  return a.filter(Set.prototype.has, new Set(b));_x000D_
}_x000D_
_x000D_
// Example:_x000D_
console.log(intersect([1,2,3], [2,3,4,5]));
_x000D_
_x000D_
_x000D_

I recommend above succinct solution which outperforms other implementations on large inputs. If performance on small inputs matters, check the alternatives below.

Alternatives and performance comparison:

See the following snippet for alternative implementations and check https://jsperf.com/array-intersection-comparison for performance comparisons.

_x000D_
_x000D_
function intersect_for(a, b) {_x000D_
  const result = [];_x000D_
  const alen = a.length;_x000D_
  const blen = b.length;_x000D_
  for (let i = 0; i < alen; ++i) {_x000D_
    const ai = a[i];_x000D_
    for (let j = 0; j < blen; ++j) {_x000D_
      if (ai === b[j]) {_x000D_
        result.push(ai);_x000D_
        break;_x000D_
      }_x000D_
    }_x000D_
  } _x000D_
  return result;_x000D_
}_x000D_
_x000D_
function intersect_filter_indexOf(a, b) {_x000D_
  return a.filter(el => b.indexOf(el) !== -1);_x000D_
}_x000D_
_x000D_
function intersect_filter_in(a, b) {_x000D_
  const map = b.reduce((map, el) => {map[el] = true; return map}, {});_x000D_
  return a.filter(el => el in map);_x000D_
}_x000D_
_x000D_
function intersect_for_in(a, b) {_x000D_
  const result = [];_x000D_
  const map = {};_x000D_
  for (let i = 0, length = b.length; i < length; ++i) {_x000D_
    map[b[i]] = true;_x000D_
  }_x000D_
  for (let i = 0, length = a.length; i < length; ++i) {_x000D_
    if (a[i] in map) result.push(a[i]);_x000D_
  }_x000D_
  return result;_x000D_
}_x000D_
_x000D_
function intersect_filter_includes(a, b) {_x000D_
  return a.filter(el => b.includes(el));_x000D_
}_x000D_
_x000D_
function intersect_filter_has_this(a, b) {_x000D_
  return a.filter(Set.prototype.has, new Set(b));_x000D_
}_x000D_
_x000D_
function intersect_filter_has_arrow(a, b) {_x000D_
  const set = new Set(b);_x000D_
  return a.filter(el => set.has(el));_x000D_
}_x000D_
_x000D_
function intersect_for_has(a, b) {_x000D_
  const result = [];_x000D_
  const set = new Set(b);_x000D_
  for (let i = 0, length = a.length; i < length; ++i) {_x000D_
    if (set.has(a[i])) result.push(a[i]);_x000D_
  }_x000D_
  return result;_x000D_
}
_x000D_
_x000D_
_x000D_

Results in Firefox 53:

  • Ops/sec on large arrays (10,000 elements):

    filter + has (this)               523 (this answer)
    for + has                         482
    for-loop + in                     279
    filter + in                       242
    for-loops                          24
    filter + includes                  14
    filter + indexOf                   10
    
  • Ops/sec on small arrays (100 elements):

    for-loop + in                 384,426
    filter + in                   192,066
    for-loops                     159,137
    filter + includes             104,068
    filter + indexOf               71,598
    filter + has (this)            43,531 (this answer)
    filter + has (arrow function)  35,588
    

Examples related to javascript

need to add a class to an element How to make a variable accessible outside a function? Hide Signs that Meteor.js was Used How to create a showdown.js markdown extension Please help me convert this script to a simple image slider Highlight Anchor Links when user manually scrolls? Summing radio input values How to execute an action before close metro app WinJS javascript, for loop defines a dynamic variable name Getting all files in directory with ajax

Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to intersection

How to calculate the intersection of two sets? Removing duplicates in the lists Intersect Two Lists in C# How can I get the intersection, union, and subset of arrays in Ruby? Intersection and union of ArrayLists in Java How to find list intersection? Simplest code for array intersection in javascript Find intersection of two nested lists?