Most Efficient Way to Find Common Item Between Arbitrary Number of Arrays

Question

I need to be able to find a common item between an arbitrary number of arrays. For example, let's say there's an object like this:

var obj = {
  a: [ 15, 23, 36, 49, 104, 211 ],
  b: [ 9, 12, 23 ],
  c: [ 11, 17, 18, 23, 38 ],
  d: [ 13, 21, 23, 27, 40, 85]
};

I'd need to determine the common item between each of these arrays. (In this case, 23).

My solution is to find the shortest array, and iterate through each item in it, checking the index of the other arrays.

var shortest = {};
var keys = [];
for ( var key in obj ) {

  if ( obj.hasOwnProperty( key ) && Array.isArray( obj[ key ] ) ) {
    keys.push( key );

    if ( !shortest.hasOwnProperty( 'length' ) || obj[ key ].length < shortest.length ) {
      shortest.name = key;
      shortest.length = obj[ key ].length;
    }
  }
}



var res = obj[ shortest.name ].filter(function ( v ) {

  for ( var i = 0; i < keys.length; i++ ) {

    if ( obj[ keys[ i ] ].indexOf( v ) === -1 ) {
      return false;
    }

    return true;
  }
};

However, this seems enormously inefficient, and I'm trying to determine if there's a better way, preferably without having to loop through things multiple times.

Answer 1

I don't think it's possible to do this in less than O(N), where N is the number of items in all arrays. Your current solution is less efficient, since indexOf is O(N) for each array, and you could run through all of them for each item in the shortest array.

I think a map-based option would be O(N):

var counts = {};
var keys = Object.keys(obj);
var arr, el;
for (var k = 0; k < keys.length; k++) {
    arr = obj[keys[k]];
    for (var i = 0; i < arr.length; i++) {
        el = arr[i];
        if (counts[el] === undefined) {
            // new value, start counting
            counts[el] = 1;
        } else {
            // increment count for this value
            counts[el]++;
            // if we have as many values as keys, we're done
            if (counts[el] === keys.length) {
                return el;
            }
        }
    }
}

Some caveats here:

• This assumes that the elements can be used as object keys (i.e. they can be uniquely converted to strings), and that you don't have some nasty edge cases like 1 and "1" in different arrays.

• This assumes the array values are unique for each array.

• This assumes there's only one element in the intersection.

https://jsfiddle.net/xzfa75og/

Answer 2

Another O(n) set union solution, coded more functionally. Elements as object keys caveat still applies although this will return the set (array) of all shared elements in the intersection.

function common(o) {
  // Map each of the object key arrays to a set.
  return Object.keys(o).map(function(k) {
    return o[k].reduce(function(a, e) {
      a[e] = 1;
      return a;
    }, {});
  }).reduce(function(a, e) {
    // Perform a set union.
    Object.keys(e).forEach(function(k) {
      if (!a[k]) {
        delete e[k];
      }
    });
    return e;
  })
}

var obj = {
  a: [ 15, 23, 36, 49, 104, 211 ],
  b: [ 9, 12, 23 ],
  c: [ 11, 17, 18, 23, 38 ],
  d: [ 13, 21, 23, 27, 40, 85]
};

common(obj);

Answer 3

I would do this job by an invention of Array.prototype.intersect(). It won't fail when there are duplicate items in the array. If you have same item duplicated in each array you will get the duplicate in the intersection as it should be. Let's see how it will work

Array.prototype.intersect = function(...a) {
      return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
    };
var obj = {
           a: [ 15, 23, 36, 49, 104, 211 ],
           b: [ 9, 12, 23 ],
           c: [ 11, 17, 18, 23, 38 ],
           d: [ 13, 21, 23, 27, 40, 85]
          },
   arrs = Object.keys(obj).map(e => obj[e]);

console.log(JSON.stringify(arrs.pop().intersect(...arrs))); // take the last one out to invoke the method over the rest

Answer 4

Just another solution in ES5 with a temporary object in O(n).

var obj = { a: [15, 23, 36, 49, 104, 211], b: [9, 12, 23, 15], c: [11, 17, 18, 23, 38], d: [13, 21, 23, 27, 40, 85] },
    result = Object.keys(obj).reduce(function (o) {
        return function (r, k, i) {
            var t = o;
            o = Object.create(null);
            return obj[k].filter(function (a) {
                return (!i || t[a]) && (o[a] = true);
            });
        };
    }(Object.create(null)), []);

console.log(result);