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
  • 11,754
  • 19
  • 53
  • 72

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,473
  • 1
  • 24
  • 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
  • 47,548
  • 10
  • 114
  • 120
  • 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
  • 137,901
  • 29
  • 269
  • 269