Symmetric Difference in Javascript

Sets

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.

--

--

--

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

Recommended from Medium

TurtlesTab Chrome Extension — a Chingu Voyage-2 project

Modern JavaScript for Ancient Web Developers

Simple Random Number Generator with React

JavaScript Research Sessions 1–5

Frequency Counter Algorithm

Baby Steps for JavScript : Events

Responsive Styling For Mobile and Web With React + Material UI

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dustin Morris

Dustin Morris

More from Medium

Javascript Array slice() method explained

[ReactJS]Front End Developer Interview Questions

Window is undefined during SSR

What is the difference between ‘==’ and ‘===’? And why you need to know.