Comparing 2 arrays for differences (find symmetric difference)

Question

This should be a simple algorithm but I can't wrap my head around the logic. I need to take 2 arrays and keep only the values that are found in one array or the other and not both.

For example if I have

arr1 [1,2,3,6]

arr2 [2,3,4,5,7]

I want to have 2 arrays again being

arr1 [1,6]
arr2 [4,5,7]

EDIT:

I removed my old code and put in some other working code. Still not very pretty but at least working. All I would need to do is store arr3 into arr1 and arr4 into arr2.

    var arr3 = [];
    var arr4 = [];

    var foundMatch = false;

    //find all arr1 elements that don't match arr2 elements
    //store into arr4
    for(var i=0; i<arr1.length; i++)
    {
        foundMatch = false;
        for(var j=0; j<arr2.length; j++)
        {
            if(arr1[i] == arr2[j])
            {
                console.log("match found for [%s] [%s]", i, j);
                foundMatch = true;
                break;
            }
        }
        if(!foundMatch)
        {
            arr4.push(arr1[i]);
        }
    }

    //find all arr2 elements not in arr1
    //store in arr3
    for(var i=0; i<arr2.length; i++)
    {
        foundMatch = false;
        for(var j=0; j<arr1.length; j++)
        {
            if(arr2[i] == arr1[j])
            {
                console.log("match found for [%s] [%s]", i, j);
                foundMatch = true;
                break;
            }
        }
        if(!foundMatch)
        {
            arr3.push(arr2[i]);
        }
    }

Don't reinvent the wheel: http://ramdajs.com/docs/#difference — Jared Smith, Apr 24 '17 at 19:20
Also note that its much, much easier to push the non-dupe values into a new array than to splice the existing ones.... — Jared Smith, Apr 24 '17 at 19:21
Here is an [existing Stack Overflow question that solves finding the _symmetric difference_ of many arrays](http://stackoverflow.com/questions/30834946/trying-to-solve-symmetric-difference-using-javascript). — savinger, Apr 24 '17 at 19:26
I don't exactly want the symmetric difference into a single array. I want each array to keep their non matching values. — Crash667, Apr 24 '17 at 19:36
@Crash667 its one of my favorites: its popular enough, well-designed enough, etc. The author is also very active on SO meaning ramda questions tend to get reasonably fast canonical answers. — Jared Smith, Apr 24 '17 at 19:38

nem035 · Accepted Answer · 2018-12-05T15:17:13.973

The fastest solution in terms of time complexity is to create a Set or a hash from one array -> O(N), then iterate through the other to compare if an element is not the set -> O(M) -> and then add it to the diffs array. The main benefit here is that Set lookup time is constant. This solution also has space complexity of O(N) for building the set.

You can repeat this for the other array as well, giving you total of O(N) + O(M) + O(N) + O(M) which, when constant factors are removed, is just O(N+M) time complexity.

Building the set for the second array gives total space complexity as O(N+M).

// Total complexity
// Time:  O(N+M)
// Space: O(N+M)

// time complexities for each step shown bellow

let N = [1,2,3,6]
let M = [2,3,4,5,7]

const setForN = new Set(N); // O(N)
const setForM = new Set(M); // O(M)

// O(N + M) at this point

const answerN = N.filter(n => !setForM.has(n)) // O(N)
const answerM = M.filter(m => !setForN.has(m)) // O(M)

// O(N + M) + O(N + M) at this point, which is just O(N + M)

console.log(answerN, answerM);

ES5 solution:

var N = [1,2,3,6]
var M = [2,3,4,5,7]

var setOfNumbers = function(arr) {
  return arr.reduce(function(set, item) {
    return Object.defineProperty(set, item, { value: item });
  }, Object.create(null));
}
var setForN = setOfNumbers(N);
var setForM = setOfNumbers(M);

var answerN = N.filter(function(n) { return typeof setForM[n] !== 'number' });
var answerM = M.filter(function(m) { return typeof setForN[m] !== 'number' });

console.log(answerN, answerM);

Another way is to do what other answers suggest which is to, for each element in N -> O(N), check if it exists in M -> O(M), and add it to the diffs array. Repeat for the other array.

This has better, constant, space complexity O(1) but slower quadratic O(N*M) time.

// Total Complexity:
// Time:  O(N*M)
// Space: O(1)

let N = [1,2,3,6]
let M = [2,3,4,5,7]

// For every element in N -> O(N)
// Iterate through M and check if it's there -> O(M)
// Total: O(N*M)
const answerN = N.filter(n => !M.includes(n));

// For every element in M -> O(M)
// Iterate through N and check if it's there -> O(N)
// Total: O(M*N)
const answerM = M.filter(m => !N.includes(m));

// O(N*M) + O(M*N) at this point, which is just O(N*M)

console.log(answerN, answerM);

score 2 · Answer 2 · answered Apr 24 '17 at 19:24

2

You're trying to get A - B and B - A for your 2 sets A and B

arr1 = [1,2,3,6]
arr2 = [2,3,4,5,7]

var required1 = arr1.filter((x) => arr2.indexOf(x) < 0)
var required2 = arr2.filter((x) => arr1.indexOf(x) < 0)

console.log(required1, required2);

answered Apr 24 '17 at 19:24

mehulmpt

15,861
12
48
88

score 0 · Answer 3 · answered Apr 24 '17 at 19:26

You can you the array filter method to check for intersection of 2 arrays: Consider the following code which create 2 new arrays that only contain unique values:

let arr1 = [1,2,3,6];
let arr2 =  [2,3,4,5,7];

let newArr1 = arr1.filter((itm)=>{
    return arr2.indexOf(itm) == -1
});

let newArr2 = arr2.filter((itm)=>{
    return arr1.indexOf(itm) == -1
});

Optout of newArr1 and newArr2 are :

[1, 6] 
[4, 5, 7]

score 0 · Answer 4 · answered Apr 24 '17 at 19:34

var arr1 = [1,2,3,6],

    arr1Copy = arr1,

    arr2 = [2,3,4,5,7];

arr1 = arr1.filter(function(outerItem){
  return !arr2.some(function(innerItem){
    return outerItem === innerItem;
  })
})

arr2 = arr2.filter(function(outerItem){
  return !arr1Copy.some(function(innerItem){
    return outerItem === innerItem;
  })
})

Comparing 2 arrays for differences (find symmetric difference)

4 Answers4