Brandon Anzaldi Brandon Anzaldi - 5 months ago 10
Javascript Question

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

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

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 there's only one element in the intersection.

https://jsfiddle.net/xzfa75og/