Simplest code for array intersection in javascript

Question

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]

Protector

Do you want simple or fast? – Fernandina

Priority is simple, but it can't be so brain-dead that it will be a performance hog :) – Protector

Adding a break to Simple js loops increases the ops/sec to ~10M – Chemoreceptor

Nice! But what if they are not numeric types? What if they are custom objects that need a custom check? – Dopester

Functions in the test return wrong results. In fact only one implementation returns the expected result. – Ariosto

Thanks for this! I forked your fiddle to see if cacheing the array lengths in the "Simple js loops" version improved it at all, since the property wouldn't have to be looked up at each iteration. It squeezed about another 1M ops/sec. – Enjoyable

This isn't as good as it first looks. First of all, intersect_safe gives a totally wrong performance impression, as you skipped the part where you have to do some sorting first! Secondly, there are a number of bugs in this, e.g. what's idx and why would SimpleJsLoops do ret.push(i); rather than ret.push(x[i]); – Nemesis

@hegemon, jsfiddle.net/nmgnL5un/1 some of them works correct(but collect indexes instead of values) – Twobyfour

The only one of the functions in the fiddle that returns correct results is the underscore library. That's not really a fair comparison. – Socialist

So I wanted to test with larger more randomized lists. The result is jsfiddle.net/aXzWw/217 – Uticas

Answer 1

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

const filteredArray = array1.filter(value => array2.includes(value));

For older browsers, with Array.prototype.indexOf and without an arrow function:

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

NB! Both .includes and .indexOf internally compares elements in the array by using ===, so if the array contains objects it will only compare object references (not their content). If you want to specify your own comparison logic, use Array.prototype.some instead.

Downtime

Best answer here, both for simplicity and working with non-numbers – Philbin

That is straight-forward and easy to maintain, but for unsorted lists, it appears to not be as fast as competitors: jsfiddle.net/aXzWw/217 – Uticas

intersection([1,2,1,1,3], [1]) returns [1, 1, 1]. Shouldn't it return just [1]? – Likeminded

Good catch. You will need a second filter. See the example here: https://mcmap.net/q/48946/-compute-intersection-of-two-arrays-in-javascript-duplicate (<-- at the end of that answer) – Leone

Good for simplicity and for small inputs but its quadratic complexity. For larger inputs there must be a better solution. – Precancel

Isn't this highly inefficient, being O(n^2). – Benedicto

re: "Shouldn't it return just [1]?" Doesn't this depend on your definition of intersection? All entries present in both arrays seems to imply [1,1,1] is valid (each 1 appears in both). And if your data allows duplicate values, why wouldn't the original result be valid? – Carisa

Maybe add something like var filteredArray = ... because it's not clear whether .filter() returns something or modifies the original array. – Spindling

When we talk about intersection typically we mean it for sets in mathematical sense, and you aren't supposed to have repeating elements, so the answer seems valid to me. – Gish

To fix the "[1, 1, 1] issue", wrap the result in Array.from(new Set(filteredArray)). Hope it helps. – Murrell

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

Warr

It's array.shift creating a new array under-the-hood with every call? – Coraciiform

I found some performance regarding shift() versus pop(): jsperf.com/pop-vs-shift-on-a-array/11 – Coraciiform

@thesmart: you're right, there are definitely more performant ways to do it. The code, above, was intended to be simple, not fast :) – Warr

.shift requires moving every element (O(n) in itself) in the array so the comment about complexity of the first version is wrong – Unorganized

The complexity should be MAX(a.length,b.length), not MIN(a.length,b.length). Big O is talking about worst cases. For cases like a = [1,2,3,4,5] and b = [6], this algorithm would run a.length times. – Maiduguri

@shawn, take a closer look. both loops stop when the shorter array length is hit, not the longer. – Warr

No, the loop stops when one of the arrays is done, not necessarily the shorter array. Check this example. – Maiduguri

The destructive version removes the advantage of requiring a sorted array: not running in quadratic time. I don’t think it even improves readability. Editing this down to just the fast, non-destructive version would make the answer much better. – Avigdor

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

Enthalpy

what's this [...setA] syntax? Some special kind of javascript operation? – Kelantan

@Kelantan that is Spread syntax and in this case it is just being used to create an array from the elements in the set. "Array.from(setA)" would also work in this case, but since the question asked for "simplest" I tried to make it cleaner to read on that line. On that matter, I think the code could be simpler, so I'll update the snippet. – Enthalpy

@Enthalpy I'm curious: why did you "clone" the array a? #filter doesn't destroy the original array, right? It creates a new array? – Alcoholic

@Alcoholic I just created an array from the set in order to remove duplicates, otherwise, using the array directly would result in returning duplicates. For example, if I used the array directly, intersect([1,2,2,4],[2,3]) would yield [2, 2]. – Enthalpy

"Note that the set implementation will only allow unique values" - that is the literal definition of a Set, not an implementation detail. – Beatabeaten

What is the advantage of using Sets? And why can't it be done with only with standard arrays? – Internecine

In the first example (removing duplicates), there’s no need to create a set from both a and intersection. Just one or the other is enough. – Avigdor

To answer @adelriosantiago... The short answer is that it's an order of complexity faster to call "has(x)" on a Set vs. array's includes(), since it's implemented with a hash function (array's includes() is O(n) lookup time, and Set's has() O(1) or constant). This is the advantage of using HashSets. If you care why it's faster, I suggest learning about the data structures HashSets & HashMaps. – Heavy

Answer 4

Using Underscore.js or lodash.js

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

Errecart

Op asked for "library-free". – Elegiac

In any case, this is the top google listing for this search so having a library answer is useful. Thanks. – Kingofarms

It is a good approach but I wonder which is faster/more-efficient: arrA.filter(e=>e.includes(arrB)) or _.intersection(arrA, arrB)? – Fateful

hey, is it possible to pass a list of lists to this function ? like [ [ { tokenId: 2 } ], [ { tokenId: 2 }, { tokenId: 3 } ] ] and expecting it to returns { tokenId: 2 } ? – Sonorous

@anshsachdeva Yes, you can javascript var objects = [ [ { tokenId: 2 } ] ] var others = [ [ { tokenId: 2 }, { tokenId: 3 } ] ] _.intersectionWith(objects, others, (a, b) => _.intersectionWith(a, b)); – Chucho

Answer 5

// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

// Example:
console.log(intersect([1,2,3], [2,3,4,5]));

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.

function intersect_for(a, b) {
  const result = [];
  const alen = a.length;
  const blen = b.length;
  for (let i = 0; i < alen; ++i) {
    const ai = a[i];
    for (let j = 0; j < blen; ++j) {
      if (ai === b[j]) {
        result.push(ai);
        break;
      }
    }
  } 
  return result;
}

function intersect_filter_indexOf(a, b) {
  return a.filter(el => b.indexOf(el) !== -1);
}

function intersect_filter_in(a, b) {
  const map = b.reduce((map, el) => {map[el] = true; return map}, {});
  return a.filter(el => el in map);
}

function intersect_for_in(a, b) {
  const result = [];
  const map = {};
  for (let i = 0, length = b.length; i < length; ++i) {
    map[b[i]] = true;
  }
  for (let i = 0, length = a.length; i < length; ++i) {
    if (a[i] in map) result.push(a[i]);
  }
  return result;
}

function intersect_filter_includes(a, b) {
  return a.filter(el => b.includes(el));
}

function intersect_filter_has_this(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

function intersect_filter_has_arrow(a, b) {
  const set = new Set(b);
  return a.filter(el => set.has(el));
}

function intersect_for_has(a, b) {
  const result = [];
  const set = new Set(b);
  for (let i = 0, length = a.length; i < length; ++i) {
    if (set.has(a[i])) result.push(a[i]);
  }
  return result;
}

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
  

Terrance

intersect([1,2,2,3], [2,3,4,5]) returns [2, 2, 3]. – Roque

@Roque Exactly. As per comment "Return elements of array a that are also in b" – Terrance

Quality answer, however the use of Sets fundamentally alters results since op's question asked only about array intersections and makes no mention/stipulation of how to handle duplicates. Shy of that, this answer may yield unexpected results when duplicates exist. – Beatabeaten

Answer 6

Simplest, fastest O(n) and shortest way:

function intersection (a, b) {
    const setA = new Set(a);
    return b.filter(value => setA.has(value));
}

console.log(intersection([1,2,3], [2,3,4,5]))

@nbarbosa has almost the same answer but he cast both arrays to Set and then back to array. Difference is that his code will return only unique records while result of this code will also contain repeated entries from array b (assuming that both arrays aren't filled with unique values).

So use which ever code fits your requirements

Polyzoic

Answer 7

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>");

Fleeting

this code looks great, but I do not understand it completely. Possible to explain it please? – Berlyn

@novembersky It gathers all subject arrays in an array like [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]] and then applies .reduce(). First [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e) operation is performed and the result becomes the new p and c becomes [4,5,6,7] in the next turn and continues so on up until there is no more c is left. – Fleeting

This is an expensive solution if you're working with large data sets. – Beatabeaten

Don't modify the prototype unnecessarily. – Latinize

…and if you do want to modify Array.prototype, at least do it correctly – Imprecate

Answer 8

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

Masao

This only stands a chance if your arrays only contain strings or numbers, and if none of the script in your page has messed with Object.prototype. – Intuitivism

The OP's example was using numbers, and if a script has messed with Object.prototype then the script should be rewritten or removed. – Masao

You don't need both (d1) and (d2). Create (d2), then loop through (a) instead of looping through (d1). – Instill

Should be d[b[i]] = true; instead of d[b[j]] = true; (i not j). But edit requires 6 chars. – Praiseworthy

@Praiseworthy thanks, fixed. (Added a // comment to get around minimum edit requirement.) – Masao

A good side-effect of this function: it guarantees that results will be sorted in the same order as the initial "a" array. For a potential speed gain, I would simple cache a.length and b.length at the beginning of the function, i.e.var d = {}, results = [], alen = a.length, blen = b.length; – Cloying

Answer 9

If you need to have it handle intersecting multiple arrays:

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

Antenatal

But how fast is this solution for 30 arrays with 100 elements ? – Cowry

This is using nothing but native to Javascript methods, and therefor the VM in which the code will run is free to optimize it as far as it can. I am quite positive that there exists no faster solution given you are running this in a modern version of V8 relative to the age of this comment. – Antenatal

@Belfordz: No, this is incredibly slow because of all the array copying and unnecessary set reconstruction. Using new Set(b).has(x) without keeping the set is even slower than just b.includes(x). – Avigdor

Answer 10

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. It's about three times faster to use .pop.

Celie

Just as a side note for others - this will only work for numbers, not strings. – Praiseworthy

Note that if you replace a[aLast] > b[bLast] with a[aLast].localeCompare(b[bLast]) > 0 (and same with the else if below) then this will work on strings. – Complected

The speed difference depends on the size of the arrays because .pop is O(1) and .shift() is O(n) – Unorganized

Answer 11

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.

Bulter

Sorting will not necessarily help for arrays of arbitrary objects – Intuitivism

If the array is not sorted, need to loop around 1,000,000 times when you intersect 1000 length array x 1000 length array – Bulter

I think you missed my point, which is that arbitrary objects in JavaScript have no natural sort order, meaning that sorting an array of arbitrary objects will not result in equal objects being grouped. It's no good having an efficient algorithm that doesn't work. – Intuitivism

Ah sorry, I missed "arbitrary objects", yes, You're right. those object cannot sort it, and the algorithm may not work on those. – Bulter

Answer 12

Using jQuery:

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

Scurvy

This could also be written as c = $(b).filter(a);, but I wouldn't recommend relying on jQuery for this sort of array manipulation since the documentation only mentions that it works for elements. – Principal

This does not answer op's question: "What's the simplest, library-free code..." – Beatabeaten

Answer 13

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"]; 

Intuitivism

This only works in the case where object identity is the only form of equality. – Masao

Well yes, but I think that's what would seem natural to most people. It's also trivial to plug in an alternative function to perform a different equality test. – Intuitivism

I think you are accidentally creating a global variable firstArr in your example. – Halfbreed

@JasonJackson: You're right, thanks. Clearly changed my mind about whether to call the variable firstArr or firstArray and didn't update all of the references. Fixed. – Intuitivism

Answer 14

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.

Incult

Answer 15

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

Williwaw

This is far the best answer with a small modification. After the var v = line add if (typeof v == 'function') continue; and it will skip adding functions to the results. Thanks! – Olivas

Thanks @Zsolti. I don't add your suggestion because having functions (and the way we want to handle it) is out of the scope of the original question. But see my edit: If you can have repetitions in your input arrays, then original implementation is buggy. I fixed it in my edit. ...On the other hand, if you know for sure that there won't be any repetition, the original implementation is slightly cheaper. – Williwaw

...about functions, they also can be intersected: If we detect them like @Olivas says (with if (typeof v == 'function'), then we can use its stringification (v.toString()) as key for the index. But, we need to do something to preserve it intact. The easiest way to do so is simply assign the original function as value instead of a simple boolean true value. But, in that case, the latest deindexaton should be also altered to detect this condition and restore the right value (the function). – Williwaw

How fast can this be with 30 arrays with 100 elements.. how is the CPU usage? – Cowry

Answer 16

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

Talcahuano

By the way, this can be easily extended to interesect any number of arrays: replace the boolean by integers, and increment each time it is seen: you can easily read the intersection on the last round. – Talcahuano

Interesting solution, I like it. Most other solutions are O(n^2), but this is O(n). I added the integer code to ericP's performance fiddle here jsfiddle.net/321juyLu/2. It came 3rd, me likey :) – Reef

Answer 17

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

Angst

Answer 18

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.

Cristophercristy

.some(x => x === item) is a complicated way to write .includes(item), and .reduce(removeDuplicates, []) is a complicated way to write a flatten + unique. This also probably gets slow faster than you think it does (easily relevant for event-based apps). – Avigdor

Answer 19

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.

Mick

Answer 20

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

Allyl

Answer 21

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.

// small, reusable auxiliary functions

const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run it

console.log( intersect(xs) (ys) );

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:

// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// de-duplication

const dedupe = comp(afrom) (createSet);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// unique result

console.log( intersect(dedupe(xs)) (ys) );

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:

// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];


// run

console.log( intersectn(xs, ys, zs) );

Kolva

Impressively functional: had to do a double-take to confirm that's not Haskell. The only nitpick is: (expr ? true : false) is redundant. Use just expr if actual booleans aren't needed, just truthy/falsy. – Slovak

Pointlessly complicated, and intersectn is inefficient. This is the wrong way to write reusable functions. – Avigdor

This answer deserves a more thoughtful critique than "pointlessly complicated". If someone stands to be influenced by it, then a comment amounting to "wrong" can only introduce confusion. – Lute

Answer 22

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

Xylem

Answer 23

This function avoids the N^2 problem, taking advantage of the power of dictionaries. Loops through each array only once, and a third and shorter loop to return the final result. It also supports numbers, strings, and objects.

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [];

    // Returns a unique reference string for the type and value of the element
    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    array1.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (!(key in mergedElems)) {
            mergedElems[key] = {elem: elem, inArray2: false};
        }
    });

    array2.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (key in mergedElems) {
            mergedElems[key].inArray2 = true;
        }
    });

    Object.values(mergedElems).forEach(function(elem) {
        if (elem.inArray2) {
            result.push(elem.elem);
        }
    });

    return result;
}

If there is a special case that cannot be solved, just by modifying the generateStrKey function, it could surely be solved. The trick of this function is that it uniquely represents each different data according to type and value.

---

This variant has some performance improvements. Avoid loops in case any array is empty. It also starts by walking through the shorter array first, so if it finds all the values of the first array in the second array, exits the loop.

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [],
        firstArray, secondArray,
        firstN = 0, 
        secondN = 0;

    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    // Executes the loops only if both arrays have values
    if (array1.length && array2.length) 
    {
        // Begins with the shortest array to optimize the algorithm
        if (array1.length < array2.length) {
            firstArray = array1;
            secondArray = array2;
        } else {
            firstArray = array2;
            secondArray = array1;            
        }

        firstArray.forEach(function(elem) {
            var key = generateStrKey(elem);
            if (!(key in mergedElems)) {
                mergedElems[key] = {elem: elem, inArray2: false};
                // Increases the counter of unique values in the first array
                firstN++;
            }
        });

        secondArray.some(function(elem) {
            var key = generateStrKey(elem);
            if (key in mergedElems) {
                if (!mergedElems[key].inArray2) {
                    mergedElems[key].inArray2 = true;
                    // Increases the counter of matches
                    secondN++;
                    // If all elements of first array have coincidence, then exits the loop
                    return (secondN === firstN);
                }
            }
        });

        Object.values(mergedElems).forEach(function(elem) {
            if (elem.inArray2) {
                result.push(elem.elem);
            }
        });
    }

    return result;
}

Cyanocobalamin

What’s the purpose of Object.prototype.toString.call(/f/) (equivalent to "[object RegExp]")? – Avigdor

Sorry, a small residual error. Corrected! is Object.prototype.toString.call(elem) allows to preserve different keys for elements of type object that have same toString() output – Cyanocobalamin

Answer 24

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

Jablonski

Not a bad reference if undesrcore is available – Kaon

Answer 25

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

Basketball

Answer 26

I think using an object internally can help with computations and could be performant too.

// Approach maintains a count of each element and works for negative elements too

function intersect(a,b){
    
    const A = {};
    a.forEach((v)=>{A[v] ? ++A[v] : A[v] = 1});
    const B = {};
    b.forEach((v)=>{B[v] ? ++B[v] : B[v] = 1});
    const C = {};
    Object.entries(A).map((x)=>C[x[0]] = Math.min(x[1],B[x[0]]))
    return Object.entries(C).map((x)=>Array(x[1]).fill(Number(x[0]))).flat();
}
const x = [1,1,-1,-1,0,0,2,2];
const y = [2,0,1,1,1,1,0,-1,-1,-1];
const result = intersect(x,y);
console.log(result);  // (7) [0, 0, 1, 1, 2, -1, -1]

Longshoreman

Answer 27

I am using map even object could be used.

//find intersection of 2 arrs
const intersections = (arr1,arr2) => {
  let arrf = arr1.concat(arr2)
  let map = new Map();
  let union = [];
  for(let i=0; i<arrf.length; i++){
    if(map.get(arrf[i])){
      map.set(arrf[i],false);
    }else{
      map.set(arrf[i],true);
    }
  }
 map.forEach((v,k)=>{if(!v){union.push(k);}})
 return union;
}

Dozen

A code-only answer is not high quality. While this code may be useful, you can improve it by saying why it works, how it works, when it should be used, and what its limitations are. Please edit your answer to include explanation and link to relevant documentation. – Encarnalize

Answer 28

This is a proposed standard: With the currently stage 2 proposal https://github.com/tc39/proposal-set-methods, you could use

mySet.intersection(mySet2);

Until then, you could use Immutable.js's Set, which inspired that proposal

Immutable.Set(mySet).intersect(mySet2)

Reiner

Answer 29

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

Hoogh

Answer 30

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

Kunin

Answer 31

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

Peppery

Answer 32

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

Allegorical

Answer 33

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

Creel

Answer 34

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

Emersen

Answer 35

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

Deferential

Answer 36

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

Modiolus

Answer 37

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

Menace

Answer 38

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

Stoichiometry

Answer 39

Here's a simple implementation for handling multiple arrays with an optional compare function:

function intersection(arrays, compareFn = (val1, val2) => (val1 === val2)) {
  if (arrays.length < 2) return arrays[0] ?? []
  const array1 = arrays[0]
  const array2 = intersection(arrays.slice(1), compareFn)
  return array1.filter(val1 => array2.some(val2 => compareFn(val1, val2)))
}

console.log(intersection([[1, 2, 3], [2, 3, 4, 5]]))
console.log(intersection([[{ id: 1 }, { id: 2 }], [{ id: 1 }, { id: 3 }]],
  (val1, val2) => val1.id === val2.id))

Infamous

Answer 40

"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]);
    }
}

Carnap

don't ever use for .. in on arrays. ever. geez. – Hornstone

Well he said "no library" so it should be safe from iterable Array prototype extensions. But ya, that's good general advice. – Carnap

in arrays you should iterate through its indexes. for() will give you also other non-numeric members, you would not ever need to touch. – Hollins