Brandon Anzaldi - 2 years ago 53
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.

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/

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download