How to 'properly' intersect two Arrays in Javascript

Question

Is There a proper way to intersect two Arrays in Javascript?

I am trying to intersect two arrays the right way but I find some difficulties

my input isn't sorted as assumed here Simplest code for array intersection in javascript

My Code :

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    var t, a = nums1,b = nums2;
    if (b.length > a.length) t = b, b = a, a = t;
    return a.filter(x => b.includes(x))
};
console.log(intersect([1, 2], [1, 1])); //[1] correct
console.log(intersect([1, 1], [1, 2])); //[1,1] wrong
console.log(intersect([1], [1, 1])); //[1,1] wrong
console.log(intersect([1, 1, 1], [1, 1])); //[1,1,1] wrong

And tried that Algorithm from that Answer : Finding the intersection of two arrays in Javascript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  var A=nums1,B=nums2;
  var m = A.reduce(function(m, v) { m[v] = 1; return m; }, {});
  return B.filter(function(v) { return m[v]; });
};
console.log(intersect([1, 2], [1, 1])); //[1,1] wrong
console.log(intersect([1, 1], [1, 2])); //[1] right
console.log(intersect([1], [1, 1])); //[1,1] wrong
console.log(intersect([1, 1, 1], [1, 1])); //[1,1] right

Also tried this :

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  return nums1.filter((n) => nums2.indexOf(n) !== -1);
};
console.log(intersect([1, 2], [1, 1])); //[1] right
console.log(intersect([1, 1], [1, 2])); //[1,1] wrong
console.log(intersect([1], [1, 1])); //[1] right
console.log(intersect([1, 1, 1], [1, 1])); //[1,1,1] wrong

Also:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  var a = nums1,b=nums2;
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
};
console.log(intersect([1, 2], [1, 1])); //[1] right
console.log(intersect([1, 1], [1, 2])); //[1] right
console.log(intersect([1], [1, 1])); //[1] right
console.log(intersect([1, 1, 1], [1, 1])); //[1] right
console.log(intersect([2,1],[1,1])); //[] wrong

Where am I mistaken ?

I'm not sure what the purpose of your question is. What kind of answer do you expect? Do you want people to "fix" each of these implementations? — Felix Kling, Feb 17 '17 at 19:52
I am trying to find the perfect algorithm which passing all test cases — solimanware, Feb 17 '17 at 19:53
What do you mean by "intersect"? Do you mean combine all values of two arrays into a single array or copy all unique values of both arrays into a new single array, or what? — Pytth, Feb 17 '17 at 19:54
http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript — sumit, Feb 17 '17 at 19:55
copy all unique values of smallest array intresecting with the bigger array into a new single array — solimanware, Feb 17 '17 at 19:55
You missed the comment in the answer that post the last example. 'asuming inputs are ordered' — vals, Feb 17 '17 at 19:56
Possible duplicate of [Simplest code for array intersection in javascript](http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript) — vals, Feb 17 '17 at 19:58
Why should `intersect([1, 1, 1], [1, 1])` yield `[1,1]`? If we're really removing duplicates, shouldn't that return `[1]`? — Scott Sauyet, Feb 17 '17 at 19:59
Yes, I'm asking *why*. Before you figure out *how* you need to explain exactly *what* you're doing. And I don't think those test cases are enough. — Scott Sauyet, Feb 17 '17 at 20:02
... And how does that match "copy all unique values of smallest array intresecting with the bigger array into a new single array"? — Scott Sauyet, Feb 17 '17 at 20:08
Lol where was my brain when I didn't soret them and use the last method ! :D ! `.sort((a,b)=>a-b)` — solimanware, Feb 17 '17 at 20:54

Nina Scholz · Answer 1 · 2017-02-17T20:04:10.733

1

You could use Map and decrement the count if found for filtering.

var intersect = function(nums1, nums2) {
    var m = new Map();
    
    nums1.forEach(a => m.set(a, (m.get(a) || 0) + 1));
    return nums2.filter(a => m.get(a) && m.set(a, m.get(a) - 1));
};

console.log(intersect([1, 2], [1, 1]));    // [1]
console.log(intersect([1, 1], [1, 2]));    // [1]
console.log(intersect([1], [1, 1]));       // [1]
console.log(intersect([1, 1, 1], [1, 1])); // [1, 1]

edited Feb 17 '17 at 20:04

answered Feb 17 '17 at 19:56

Nina Scholz

376,160
25
347
392

The last one should return `[1, 1]` though. Both arrays contain *two* `1`s. – Felix Kling Feb 17 '17 at 19:57
Can u explain a bit ? – solimanware Feb 17 '17 at 20:09
basically it takes a count of every element and filter if the value is not `0`. then decrement the count. otherwise return false for `Array#filter`. – Nina Scholz Feb 17 '17 at 20:16
Your code is working "just" like charm any more breaking down it ? – solimanware Feb 17 '17 at 20:26
1

+1 for the god-awful, and yet still awesome, continual mutation of your helper structure and for making two statements into a single `&&` expression where the second clause is only there for it mutational side-effects. Somewhere John Backus is weeping. – Scott Sauyet Feb 17 '17 at 20:47

score 1 · Answer 2 · answered Feb 17 '17 at 20:08

1

One more implementation, using your approach 1 but removing the duplicates using the ES 6 Set

    /**
     * @param {number[]} nums1
     * @param {number[]} nums2
     * @return {number[]}
     */
    var intersect = function(nums1, nums2) {
         var result = nums1.filter(x => nums2.includes(x));
         return [...new Set(result)];
    };

    console.log(intersect([1, 2], [1, 1])); //[1] correct
    console.log(intersect([1, 1], [1, 2])); //[1] correct
    console.log(intersect([1], [1, 1])); //[1] correct
    console.log(intersect([1, 1, 1], [1, 1])); //[1] correct
    console.log(intersect([1, 45, 143, 76, 11], [761,76, 11, 1])); //[1,76,11] correct

answered Feb 17 '17 at 20:08

Abhinav Galodha

9,293
2
31
41

`[1, 1, 1], [1, 1]` should return `[1,1]` – solimanware Feb 17 '17 at 20:09
what is your logic for intersection ? – Abhinav Galodha Feb 17 '17 at 20:13
Each element in the result should appear as many times as it shows in both arrays. – solimanware Feb 17 '17 at 20:14
1

That's very different from what was said above. – Scott Sauyet Feb 17 '17 at 20:25

score 1 · Accepted Answer · answered Feb 17 '17 at 21:29

1

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    var arr = [], ind;
    while (nums1.length) {
        ind = nums2.indexOf(nums1.shift());
        if (ind > -1) {
            arr.push(nums2.splice(ind, 1)[0]);
        }
    }
    return arr;
};

answered Feb 17 '17 at 21:29

zakariamouhid

81
1
4

Perfect and so easy to understand ! – solimanware Feb 17 '17 at 21:30
you are mutilating `nums2`. – Nina Scholz Feb 17 '17 at 22:16
@NinaScholz yes, if you don't want to remove nums2 you can create copy of it `copy2 = nums2.slice(0)` – zakariamouhid Feb 18 '17 at 15:32

How to 'properly' intersect two Arrays in Javascript

Is There a proper way to intersect two Arrays in Javascript?

3 Answers3