freeCodeCamp Challenge Guide: Find the Symmetric Difference

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 Δ B) Δ C.

Relevant Links


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 ⋂ B) ⋂ C = {1, 4} &Intersection {3, 4, 5}
A ⋂ 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.

Relevant Links

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.

Relevant Links

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.

Relevant Links

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{
      result.add(val)
    }
  }
  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.

Relevant Links

7 Likes