1

I have n arrays or variable length

arr1 = [1,2,3]
arr2 = [1,3,5,8]
....

How can I compute the intersection of those n arrays ?

Running Turtle
  • 12,360
  • 20
  • 55
  • 73

3 Answers3

2

Consider checking out underscore.js library. It provides function for what you need and a bunch of other usefull functions.

Example from docs:

_.intersection([1, 2, 3], [101, 2, 1, 10], [2, 1]);
=> [1, 2]

Simple plain JS implementation can be found here. Same idea in CoffeeScript:

intersect_all = (lists) ->
  if lists.length is 0
    return []
  else return lists[0]  if lists.length is 1
  partialInt = lists[0]
  i = 1

  while i < lists.length
    partialInt = intersection(partialInt, lists[i])
    i++
  partialInt
Community
  • 1
  • 1
vbo
  • 13,583
  • 1
  • 25
  • 33
1

The most efficient way is to use hashsets:

function hashset (elements) {
  var i, set = {};
  if (!Array.isArray(elements)) return elements;
  for (i = 0; i < elements.length; i++) {
    set[elements[i]] = true;
  }
  return set;
};

function intersect (a, b) {
  var k
    , s1 = hashset(a)
    , s2 = hashset(b)
    , s3 = {}
  for (k in s1) {
    if (s2[k]) s3[k] = true;
  }
  return s3;
};

Object.keys(intersect(arr1,arr2));
// ["1", "3"]

You will find CoffeeScript source of this code, benchmarks for it and some additional information in this question.

If you're going to to intersect huge arrays then I strongly recommend you to use this approach.

Leonid Beschastny
  • 50,364
  • 10
  • 118
  • 122
  • 1
    There is a big caveat here: this only works if the arrays hold strings or if you're okay with comparing the elements as strings. – mu is too short Jan 16 '14 at 17:42
0

Either just use something like _.intersection or study the source of that implementation and rewrite it if you like.

Peter Lyons
  • 142,938
  • 30
  • 279
  • 274