Symmetric Difference in Javascript

The mathematical term symmetric difference(∆) of two sets is the set of elements which are in either of the two sets but not in both. For example:

A = [1, 2, 3, 4]
B = [3,4,5,6]
A∆B = [1,2,5,6]

Embarrassing First Attempt

Embarrassingly, my first attempt at solving the problem is seen below. My basic thought process was to sort the arrays and then move the pointers one by one looking for the same value. If the value was present in both arrays, set the values to null in both arrays. Then iterate through both arrays once again pushing the results only that were non-null.

This method had several issues. It did not account for duplicate values in the arrays. I solved this by creating a Set of the values but that still was not a satisfying solution. Sorting the arrays every iteration increased the time complexity. Additionally, it isn’t immediately clear what is happening in the functions.

Using Sets are much more elegant

My next attempt went straight to using Sets in Javascript. My approach this time was to simply iterate through one of the sets and check to see if the value was in the result set. If it was, delete it from the result set. If not, add it to the result set.

I ran into a slight issue creating this method. Using the built in reduce function in Javascript without an initializing argument will automatically use the first value as the accumulator value for the reducer function. Since my arguments are arrays, the first value is an array and not a Set with the methods ‘has’, ‘delete’, or ‘add’. My first thought was to pass the first value initializing it as a Set but then the reduce function will process the first value in the array by default and it would exclude my first Set!

So my next thought was I could check if the accumulator was an array using

`if(Array.isArray(acc)) {  acc = new Set(acc);}`

Or conversely, check to see if the accumulator was a Set using

`if(!(acc instanceof Set)) {  acc = new Set(acc);}ORif(acc.constructor.name === 'Set') {  acc = new Set(acc);}`

Can it be better?

My final settled on solution was to just pass an empty Set in the reduce function as shown below in my final solution. This causes the reduce function to use the first value with the trade off of iterating through the first value against an empty set. However, each iteration will not check to see if it is an array or not. This solution may or may not be better depending on the number of arguments passed and the length of the argument arrays because of the first empty iteration.

--

--

--

More from Dustin Morris

Love podcasts or audiobooks? Learn on the go with our new app.