 # Find the Symmetric Difference

## Problem Explanation

Symmetric difference (commonly denoted by Δ) of two sets is the set of elements which are in either of the two sets, but not in both.

For example, `sym([1, 2, 3], [5, 2, 1, 4])` should yield `[3, 4, 5]`.

Following above definition, symmetric difference of three sets A, B, and C can be expressed as `(A &Delta; B) &Delta; C`.

## Hints

### Hint 1

The arguments object is Array-like object that only inherits `Array.length` property. Hence consider converting it to an actual Array.

### Hint 2

Deem writing a helper function that returns the symmetric difference of two arrays on each call instead of attempting to difference all sets simultaneously.

### Hint 3

Apply helper function against the created arguments array reducing its elements pairwise recursively to form the expected output.

Note
In the event of odd number of sets the symmetric difference will include identical elements present in all given sets. For instance;

``````A = {1, 2, 3}
B = {2, 3, 4}
C = {3, 4, 5}

(A &Intersection; B) &Intersection; C = {1, 4} &Intersection {3, 4, 5}
A &Intersection; B = {1, 3, 5}
``````

## Solutions

Solution 1 (Click to Show/Hide)
``````function sym() {
var args = [];
for (var i = 0; i < arguments.length; i++) {
args.push(arguments[i]);
}

function symDiff(arrayOne, arrayTwo) {
var result = [];

arrayOne.forEach(function(item) {
if (arrayTwo.indexOf(item) < 0 && result.indexOf(item) < 0) {
result.push(item);
}
});

arrayTwo.forEach(function(item) {
if (arrayOne.indexOf(item) < 0 && result.indexOf(item) < 0) {
result.push(item);
}
});

return result;
}

// Apply reduce method to args array, using the symDiff function
return args.reduce(symDiff);
}
``````

#### Code Explanation

• `push()` is used to break down the arguments object to an array, args.
• The `symDiff` function finds the symmetric difference between two sets. It is used as a callback function for the `reduce()` method called on args.
• `arrayOne.forEach()` pushes the elements to result which are present only in arrayOne as well as not already a part of result.
• `arrayTwo.forEach()` pushes the elements to result which are present only in arrayTwo as well as not already a part of result.
• The result, which is the symmetric difference is returned. This solution works for any number of sets.

Solution 2 (Click to Show/Hide)
``````function sym() {
// Convert the argument object into a proper array
var args = Array.prototype.slice.call(arguments);

// Return the symmetric difference of 2 arrays
var getDiff = function(arr1, arr2) {
// Returns items in arr1 that don't exist in arr2
function filterFunction(arr1, arr2) {
return arr1.filter(function(item) {
return arr2.indexOf(item) === -1;
});
}

// Run filter function on each array against the other
return filterFunction(arr1, arr2).concat(filterFunction(arr2, arr1));
};

// Reduce all arguments getting the difference of them
var summary = args.reduce(getDiff, []);

// Run filter function to get the unique values
var unique = summary.filter(function(elem, index, self) {
return index === self.indexOf(elem);
});
return unique;
}

// test here
sym([1, 2, 3], [5, 2, 1, 4]);
``````

#### Code Explanation

• The `slice()` method is used to break down the arguments object to an array, args.
• The `getDiff` function finds the symmetric difference between two sets, arr1 and arr2. It is used as a callback function for the `reduce()` method called on args.
• The first `filterFunction()` returns elements in arr1 that don’t exist in arr2.
• The next `filterFunction()` is run on each array against the other to check the inverse of the first check for uniqueness and concatenate it.
• summary consists of the reduced arguments.
• `filter()` is used on summary to keep only the unique values and unique is returned.

Solution 3 (Click to Show/Hide)
``````const diff = (arr1, arr2) => [
...arr1.filter(e => !arr2.includes(e)),
...arr2.filter(e => !arr1.includes(e))
];

const sym = (...args) => [...new Set(args.reduce(diff))];

// test here
sym([1, 2, 3], [5, 2, 1, 4]);
``````

#### Code Explanation

• The main function sym() reduces given arrays utilising helper function diff() to a single array. Also, it temporary converts the result to Set to remove duplicates.

• The function diff() returns the symmetric difference of two arrays by picking out elements in parameterised arrays; arr1 and arr2.

2 Likes

# Advanced Solution with O(n) time complexity

Background:
So far, all three of the solutions given run in `O(n^2)` time (Technically `O(n*m)`, where `n` and `m` are the lengths of the sets). This means that as your arrays get longer, the amount of computing power you need is going to increase exponentially.

Why is this the case? Under the hood, the `Array.includes()` and the `Array.filter()` methos work by looping over your entire array and checking a condition.

Let’s imagine we’ve got two arrays, a:`[1,8,3]` and b:`[12,6,2]`. In each of the previous solutions, we would check `a.includes(b[i])`. First, we’d take the `12` from array `b`. We check it against the `1`, then the `8`, then the `3`. After determining that `12` is not equal to any of them, `a.includes(b[i])` would return `false`. That’s fine if we’re just checking a single value, but we have to check the entire array- each item in `b` takes a full loop through `a` in order to figure it out. So, if the size of `b` increases by one, you have to take yet another full trip through every item in `a`, and vice-versa.

How can we make this more efficient?

There’s a bit of trickery involved. Objects in Javascript don’t have to be looped through in order to retrieve a value. This happens through the process of hashing (probably out of the scope of this article, but go look it up). In ES6, the `Set` datastructure takes advantage of a similar strategy to be able to determine if an item is or isn’t included in it in `O(1)` (constant) time. in addition, we can both add and remove items from a set in `O(1)` time.

``````function sym(...args){
return [...args.reduce(reducer, new Set())]
}

function reducer(result, arr){
const compare = new Set(arr);
for(let val of compare){
if(result.has(val)){
result.delete(val);
}else{
}
}
return result;
}
``````

Code Explanation

Essentially, it’s similar to Solution 3, but takes advantage of the `Set` both to remove duplicates and to quickly do the equivalent of an `includes` check without having to iterate over everything. It’s a little more complicated, but computes in `O(n)` (linear) time. The difference here is that, rather than maintaining an `Array` of all the values that meet the criteria for symmetric difference, we do so with a `Set`, which we will later convert back to an `Array`.

• First, we create a `Set` called `compare` from the items in our current array. This will create a data structure that holds the unique values from the array we’re comparing against our accumulator `Set`.

• We can iterate over a `Set` using a `for ...of` loop, similar to an array. If our accumulator `Set` has the item, we delete it. If not, we add it.

• We do this with each array in the array of arrays, adding and removing values from our accumulator `Set` until we’ve iterated through all of our arrays, and each of the values inside of them.

• The reducer function will return out our accumulated `Set`. We then just use the spread operator to convert it back into an array.