Finding matches between multiple JavaScript Arrays

Question

I have multiple arrays with string values and I want to compare them and only keep the matching results that are identical between ALL of them.

Given this example code:

var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
var arr2 = ['taco', 'fish', 'apple', 'pizza'];
var arr3 = ['banana', 'pizza', 'fish', 'apple'];

I would like to to produce the following array that contains matches from all given arrays:

['apple', 'fish', 'pizza']

I know I can combine all the arrays with var newArr = arr1.concat(arr2, arr3); but that just give me an array with everything, plus the duplicates. Can this be done easily without needing the overhead of libraries such as underscore.js?

(Great, and now i'm hungry too!)

EDIT I suppose I should mention that there could be an unknown amount of arrays, I was just using 3 as an example.

Answer 1

var result = arrays.shift().filter(function(v) {
    return arrays.every(function(a) {
        return a.indexOf(v) !== -1;
    });
});

DEMO: http://jsfiddle.net/nWjcp/2/

You could first sort the outer Array to get the shortest Array at the beginning...

arrays.sort(function(a, b) {
    return a.length - b.length;
});

---

For completeness, here's a solution that deals with duplicates in the Arrays. It uses .reduce() instead of .filter()...

var result = arrays.shift().reduce(function(res, v) {
    if (res.indexOf(v) === -1 && arrays.every(function(a) {
        return a.indexOf(v) !== -1;
    })) res.push(v);
    return res;
}, []);

DEMO: http://jsfiddle.net/nWjcp/4/

Answer 2

Assuming there is an array of arrays those we want to find the intersection of, a simplest single liner approach could be

var arr = [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7]],
    int = arr.reduce((p,c) => p.filter(e => c.includes(e)));

document.write("<pre>" + JSON.stringify(int) + "</pre>");

Answer 3

Now, that you've added an indeterminate number of arrays to the question, here's another approach that collects the count for each item into an object and then collates the items that have the max count.

Advantages of this approach:

1. ~15x faster that brute force search options (used by other answers) if arrays are larger
2. Does not require ES5 or ES5 shim (works with all browsers)
3. Completely non-destructive (doesn't change source data at all)
4. Handles duplicates items in source arrays
5. Handles an arbitrary number of input arrays

And here's the code:

function containsAll(/* pass all arrays here */) {
    var output = [];
    var cntObj = {};
    var array, item, cnt;
    // for each array passed as an argument to the function
    for (var i = 0; i < arguments.length; i++) {
        array = arguments[i];
        // for each element in the array
        for (var j = 0; j < array.length; j++) {
            item = "-" + array[j];
            cnt = cntObj[item] || 0;
            // if cnt is exactly the number of previous arrays, 
            // then increment by one so we count only one per array
            if (cnt == i) {
                cntObj[item] = cnt + 1;
            }
        }
    }
    // now collect all results that are in all arrays
    for (item in cntObj) {
        if (cntObj.hasOwnProperty(item) && cntObj[item] === arguments.length) {
            output.push(item.substring(1));
        }
    }
    return(output);
}    

Working demo: http://jsfiddle.net/jfriend00/52mAP/

FYI, this does not require ES5 so will work in all browsers without a shim.

In a performance test on 15 arrays each 1000 long, this was more than 10x faster than the search method used in am not i am's answer in this jsperf: http://jsperf.com/in-all-arrays.

---

Here's a version that uses an ES6 Map and Set to de-dup and keep track of counts. This has the advantage that the type of data is preserved and can be anything (it doesn't even have to have a natural string conversion, the data can even be objects though objects are compared for being the exact same object, not having the same properties/values).

var arrays = [
    ['valueOf', 'toString','apple', 'orange', 'banana', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza', 1, 2, 999, 888],
    ['valueOf', 'toString','taco', 'fish', 'fish', 'apple', 'pizza', 1, 999, 777, 999, 1],
    ['valueOf', 'toString','banana', 'pizza', 'fish', 'apple', 'apple', 1, 2, 999, 666, 555]
    ];
    
// subclass for updating cnts    
class MapCnt extends Map {
    constructor(iterable) {
        super(iterable);
    }
    
    cnt(iterable) {
        // make sure items from the array are unique
        let set = new Set(iterable);
        // now update the cnt for each item in the set
        for (let item of set) {
            let cnt = this.get(item) || 0;
            ++cnt;
            this.set(item, cnt);
        }
    }
}


function containsAll(...allArrays) {
    let cntObj = new MapCnt();
    for (array of allArrays) {
        cntObj.cnt(array);
    }
    // now see how many items have the full cnt
    let output = [];
    for (var [item, cnt] of cntObj.entries()) {
        if (cnt === allArrays.length) {
            output.push(item);
        }
    }
    return(output);
}    

var result = containsAll.apply(this, arrays);

document.body.innerHTML = "<pre>[<br>    " + result.join(',<br>    ') + "<br>]</pre>";

Answer 4

A couple thoughts- you can compare just the items in the shortest array, and prevent duplicates in the returned array.

function arraysInCommon(arrays){
    var i, common,
    L= arrays.length, min= Infinity;
    while(L){
        if(arrays[--L].length<min){
            min= arrays[L].length;
            i= L;
        }
    }
    common= arrays.splice(i, 1)[0];
    return common.filter(function(itm, indx){
        if(common.indexOf(itm)== indx){
            return arrays.every(function(arr){
                return arr.indexOf(itm)!= -1;
            });
        }
    });
}

var arr1= ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
var arr2= ['taco', 'fish', 'apple', 'pizza', 'apple','apple'];
var arr3= ['banana', 'pizza', 'fish', 'apple','fish'];

var allArrays = [arr1,arr2,arr3];

arraysInCommon(allArrays).sort();

returned value: apple,fish,pizza

DEMO - http://jsfiddle.net/kMcud/

Answer 5

    // The easiest way!! 
    
    var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
    var arr2 = ['taco', 'fish', 'apple', 'pizza'];
    var arr3 = ['banana', 'pizza', 'fish', 'apple'];
    var arr4 = [];


    for(let i of arr1){
      if(arr2.includes(i) && arr3.includes(i)){
        arr4.push(i)
      }
    }

    console.log(arr4)


------------- OR -----------------


arr4 = arr1.filter(value => arr2.includes(value) && arr3.includes(value))

Answer 6

Assuming array of arrays and checking through all arrays:

DEMO: http://jsfiddle.net/qUQHW/

var tmp = {};
for (i = 0; i < data.length; i++) {
    for (j = 0; j < data[i].length; j++) {
        if (!tmp[data[i][j]]) {
            tmp[data[i][j]] = 0;
        }
        tmp[data[i][j]]++;
    }
}

var results = $.map(tmp, function(val,key) {
    return val == data.length ? key :null;
})

Answer 7

Here goes a single-line solution. You can split it into two thinking steps:

1. Calculate join/intersection between two arrays

var arrA = [1,2,3,4,5];
var arrB = [4,5,10];
var innerJoin = arrA.filter(el=>arrB.includes(el));
console.log(`Intersection is: ${innerJoin}`);

2. Reduce the content: calculate the intersection between the acumulated intersection and the next array.

var arrays = [
 ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'],
 ['taco', 'fish', 'apple', 'pizza'],
 ['banana', 'pizza', 'fish', 'apple']
];
var join = arrays.reduce((join, current) => join.filter(el => current.includes(el)));
console.log(`Intersection is: ${join}`);

Answer 8

This should work for any number of arrays:

function intersection(arr1, arr2) {
  var temp = [];

  for (var i in arr1) {
    var element = arr1[i];

    if (arr2.indexOf(element) > -1) {
      temp.push(element);
    }
  }

  return temp;
}

function multi_intersect() {
  var arrays = Array.prototype.slice.apply(arguments).slice(1);
  var temp = arguments[0];

  for (var i in arrays) {
    temp = intersection(arrays[i], temp);

    if (temp == []) {
      break;
    }
  }

  return temp;
}

var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
var arr2 = ['taco', 'fish', 'apple', 'pizza'];
var arr3 = ['banana', 'pizza', 'fish', 'apple'];

multi_intersect(arr1, arr2, arr3);

Answer 9

Just for the heck of it, another long hand approach:

function getCommon(a) {

  // default result is copy of first array
  var result = a[0].slice();
  var mem, arr, found = false;

  // For each member of result, see if it's in all other arrays
  // Go backwards so can splice missing entries
  var i = result.length;

  while (i--) {
    mem = result[i];

    // Check in each array
    for (var j=1, jLen=a.length; j<jLen; j++) {
      arr = a[j];
      found = false;

      // For each member of arr and until found
      var k = arr.length;
      while (k-- && !found) {

        // If found in this array, set found to true
        if (mem == arr[k]) {
          found = true;
        }
      }
      // if word wasn't found in this array, remove it from result and 
      // start on next member of result, skip remaining arrays.
      if (!found) {
        result.splice(i,1);
        break;
      }
    }
  }
  return result;
}

var data = [
  ['taco', 'fish', 'apple', 'pizza', 'mango', 'pear'],
  ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'],
  ['banana', 'pizza', 'fish', 'apple'],
  ['banana', 'pizza', 'fish', 'apple', 'mango', 'pear']
];

Edit

Function to find never enumerable properties based on thise on Object.prototype:

// Return an array of Object.prototype property names that are not enumerable
// even when added directly to an object.
// Can be helpful with IE as properties like toString are not enumerable even
// when added to an object.
function getNeverEnumerables() {

    // List of Object.prototype property names plus a random name for testing
    var spNames = 'constructor toString toLocaleString valueOf ' +
                  'hasOwnProperty isPrototypeOf propertyIsEnumerable foo';

    var spObj = {foo:'', 'constructor':'', 'toString':'', 'toLocaleString':'', 'valueOf':'',
                 'hasOwnProperty':'', 'isPrototypeOf':'', 'propertyIsEnumerable':''};

    var re = [];

    // BUild list of enumerable names in spObj
    for (var p in spObj) {
      re.push(p); 
    }

    // Remove enumerable names from spNames and turn into an array
    re = new RegExp('(^|\\s)' + re.join('|') + '(\\s|$)','g');
    return spNames.replace(re, ' ').replace(/(^\s+)|\s\s+|(\s+$)/g,'').split(' ');
}

document.write(getNeverEnumerables().join('<br>'));

Answer 10

This is essentially a compilation of all the answers boiled down:

  // Intersect any number of arrays:

 function intersect() {

   // - Arguments -> traditional array,
   // - First item ( arrays[0] ) = shortest to reduce iterations
   var arrays = Array.prototype.slice.call(arguments).sort(function(a, b) {
     return a.length - b.length;
   });

   // Use first array[0] as the base.
   var a = arrays.shift();

   var result = [];
   for (var i = a.length; i--;) {

     var val = a[i];

     // Prevent duplicates
     if (result.indexOf(val) < 0) {

       // Seek
       var found = true;
       for (var ii = arrays.length; ii--;) {
         if (arrays[ii].indexOf(val) < 0) {
           found = false;
           break;
         }
       }

       if (found) {
         result.push(val);
       }

     }

   }

   return result;

 }

 /*
 // Slower, but smaller code-base:
 function intersect (){
  
  // - Arguments -> traditional array,
  // - First item ( arrays[0] ) = shortest to reduce iterations
  var arrays = Array.prototype.slice.call(arguments).sort(function(a, b) {
         return a.length - b.length;
     });
  
  // Use first array[0] as the base.
  var a = arrays.shift();

  return a.filter(function (val, idx, aa) {
   
      // Seek
                  for(var i=arrays.length; i--;){
                      if (arrays[i].indexOf(val) < 0) {
           return false;
          }
                  }
      
      // Prevent duplicates
                  return aa.indexOf(val) === idx;
  
     });

 }
 */

 var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
 var arr2 = ['taco', 'fish', 'apple', 'pizza', 'apple', 'apple'];
 var arr3 = ['banana', 'pizza', 'fish', 'apple', 'fish'];

 var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
 var arr2 = ['taco', 'fish', 'apple', 'pizza', 'apple', 'apple'];
 var arr3 = ['banana', 'pizza', 'fish', 'apple', 'fish'];


 var result = intersect(arr1, arr2, arr3);

  // For fiddle output:
 var elem = document.getElementById("result");
 elem.innerHTML = JSON.stringify(result);
 console.log(result);

<div id="result">Results</div>

Answer 11

You can use array#reduce and array#filter. For each array, get all unique values and in a Map lookup and keep their count. Once done, array#filter this lookup based on the length of array.

const commonElements = (...arr) => {
  const lookup = arr.reduce((map, a) => {
    const unique = [...new Set(a)];
    unique.forEach(v => {
      map.set(v, (map.get(v) || 0) + 1)
    });
    return map;
  },new Map());
  return [...lookup.keys()].filter(k => lookup.get(k) === arr.length);
}

const arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'],
      arr2 = ['taco', 'fish', 'apple', 'pizza'],
      arr3 = ['banana', 'pizza', 'fish', 'apple'];
console.log(commonElements(arr1,arr2,arr3));

Answer 12

Another one solution:

const arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
const arr2 = ['taco', 'fish', 'apple', 'pizza'];
const arr3 = ['banana', 'pizza', 'fish', 'apple'];
const combinedArr = [arr1, arr2, arr3];

const result  = combinedArr
    .flatMap(([...values]) => values)
    .filter((value, index, coll) => (coll.indexOf(value) === index) && combinedArr.every(
        (values) => values.includes(value)
    ));
    
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 13

This approach counts the number of each item. After all arrays have been iterated, the counts that equal the number of arrays are selected.

To be generic, the function accepts an array of arrays, and comparison function to generate the map key in cases where you are using objects instead of primitive values.

It returns an array of common values, using the instance from the first array as the reference.

function commonValues<T>(arrays: T[][], keyFn: (item: T) => string): T[] {
  const counts: Record<any, { count: number, item: T }> = {}
  for (const array of arrays) {
    for (const item of array) {
      const key = keyFn(item)
      let entry = counts[key]
      if (!entry) {
        entry = {count: 0, item}
        counts[key] = entry
      }
      entry.count++
    }
  }
  return Object.values(counts)
      .filter(it => it.count === arrays.length)
      .map(it => it.item)
}

// For this basic example, the key function simply returns the string.

var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
var arr2 = ['taco', 'fish', 'apple', 'pizza'];
var arr3 = ['banana', 'pizza', 'fish', 'apple'];

const common = commonItems([arr1,arr2,arr3], it=>it)

function commonValues(arrays, keyFn) {
  const counts = {}
  for (const array of arrays) {
    for (const item of array) {
      const key = keyFn(item)
      let entry = counts[key]
      if (!entry) {
        entry = {count: 0, item}
        counts[key] = entry
      }
      entry.count++
    }
  }
  return Object.values(counts)
      .filter(it => it.count === arrays.length)
      .map(it => it.item)
}

var arr1 = ['apple', 'orange', 'banana', 'pear', 'fish', 'pancake', 'taco', 'pizza'];
var arr2 = ['taco', 'fish', 'apple', 'pizza'];
var arr3 = ['banana', 'pizza', 'fish', 'apple'];

const found = commonValues([arr1,arr2,arr3], it=>it)

console.log('common', found)