Javascript array match with less complexity

Question

For example

inputarray = [1, 4, 5, 9];
array1 = [1, 2, 3, 4, 5, 6, 7];
array2 = [8, 9, 10, 11, 12, 13, 14];

I would like to match inputarray with both array1 & array2.In this current scenario 1,4,5 belongs to the array1 and 9 belongs to the second array.I am expecting the output like

outputarray1=[1,4,5]
outputarray2=[9]

Suggest me best way to do this problem.I mean with less complexity.Thanks in advance.

if you have a complex solution already done... share it... else have you tried anything — Arun P Johny, Jul 08 '15 at 07:12
Refer to this http://stackoverflow.com/questions/11286979/how-to-search-in-an-array-in-node-js-in-a-non-blocking-way the complexity for this answer is N. — Josua Marcel C, Jul 08 '15 at 07:14
What if `array1` and `array2` overlap? What if they are the same? What's the current complexity? Do you mean "less complexity" in terms of asymptotic behaviour? Or in terms of performance? How is this related to node.js? — Zeta, Jul 08 '15 at 07:15
@JosuaMarcelChrisano: For a ___single___ item. For `k` items it's usually O(n \* k), unless you have some precondition. — Zeta, Jul 08 '15 at 07:17
Possible solution [link](http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript) http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript — harshs08, Jul 08 '15 at 07:17

dting · Answer 1 · 2015-07-08T09:16:07.210

At the cost of space, you can make hash objects and have constant time lookups for contains instead of using O(n) indexOf calls or for loops:

var inputarray = [1, 4, 5, 9];
var array1 = [1, 2, 3, 4, 5, 6, 7];
var array2 = [8, 9, 10, 11, 12, 13, 14];

var array1Hash = Object.create(null);
var array2Hash = Object.create(null);

var outputarray1 = [];
var outputarray2 = [];

array1.forEach(function(e) {
  array1Hash[e] = true;
});
array2.forEach(function(e) {
  array2Hash[e] = true;
});

inputarray.forEach(function(e) {
  if (e in array1Hash) {
    outputarray1.push(e);
  }
  if (e in array2Hash) {
    outputarray2.push(e);
  }
});

document.getElementById('out1').innerHTML = JSON.stringify(outputarray1);
document.getElementById('out2').innerHTML = JSON.stringify(outputarray2);

<pre id="out1"></pre>
<pre id="out2"></pre>

score 0 · Answer 2 · answered Jul 08 '15 at 07:19

You can use Array.prototype.filter for it:

var inputarray = [1,4,5,9];
var array1 = [1,2,3,4,5,6,7];
var array2 = [8,9,10,11,12,13,14];

function matchEqualElements(arrayToCompare) {

    return function (element) {
        return (arrayToCompare.indexOf(element) !== -1);
    }
}

console.log(inputarray.filter(matchEqualElements(array1)));

console.log(inputarray.filter(matchEqualElements(array2)));

score 0 · Answer 3 · answered Jul 08 '15 at 07:21

You can use this

var inputarray = [1, 4, 5, 9],
     array1 = [1, 2, 3, 4, 5, 6, 7],
     array2 = [8, 9, 10, 11, 12, 13, 14],
    outputarray1=[],outputarray2=[];

     inputarray.map(function(item){
       for(var i=0;i<array1.length;i++){
         if(array1[i]==item)outputarray1.push(item);
       }
       for(var i=0;i<array2.length;i++){
         if(array2[i]==item)outputarray2.push(item);
       }
     });
    alert(outputarray1);
    alert(outputarray2);

score 0 · Answer 4 · answered Jul 08 '15 at 07:37

Complexity in terms of less code? There's a library for that: Underscore#intersection.

inputarray = [1, 4, 5, 9];
array1 = [1, 2, 3, 4, 5, 6, 7];
array2 = [8, 9, 10, 11, 12, 13, 14];    
_.union(inputarray, array1);
_.union(inputarray, array2);

Output:

=> [1, 4, 5]
=> [9]

Algorithmic complexity, you're probably looking at O(n*m) worst case, but you could optimize with sorted arrays.

function intersection(a1, a2) {
  var results = [],
    i = 0,
    j = 0;

  while (i < a1.length && j < a2.length) {
    if (a1[i] === a2[j]) {
      results.push(a1[i]);
      i++;
      j++;
    } else if (a1[i] > a2[j]) {
      j++;
    } else if (a1[i] < a2[j]) {
      i++;
    }
  }

  return results;
}

console.log(intersection([1, 2, 3, 4, 5], [3, 5, 6, 7]));
// [3, 5]
console.log(intersection([1, 2, 3, 4, 5], [1, 2, 5, 6]));
// [1, 2, 5]

This gets you O(n+m) which if n >>> m, is just O(n).

Javascript array match with less complexity

4 Answers4