Symmetric difference between two arrays - warning: contains a solution

1

So, I solved this one with this:

function diffArray(arr1, arr2) {
  var newArr = [];
  newArr = arr1.diff(arr2);
  newArr = newArr.concat(arr2.diff(arr1));
  return newArr;
}
Array.prototype.diff = function(a){
  return this.filter(function (i){return a.indexOf(i) < 0;});
};

I am just wondering how other solved this challenge and if anyone came up with a solution that is simpler/more efficient.

Thanks!

1 Like
2

Hi!
I like that your solution uses the filter and is readable.

Here is a solution that I have coded. In this solution you don’t loop on the elements of the second array.
I am not sure that it is more efficient, I can’t think of a way of doing it better than O(n²).

function diffArray(arr1, arr2) {    

var newArr = []; 

for(var i = 0; i < arr1.length; i++) {
var indexEl = arr2.indexOf(arr1[i]);

//If element is unique in arr1, we keep it
if( indexEl === -1)
  {
    newArr = newArr.concat(arr1[i]);
  }
//If element is in arr2, we remove it from arr2
else
  {
    arr2.splice(indexEl,1);
  }
}

//All the elements remaining in arr2 are unique
//So we need to return them as well
newArr = newArr.concat(arr2);

return newArr;
}
3

I think I see how you could do this in O(n) time with a hash table (Javascript object). For instance, to compare two arrays, you could keep a javascript object for each and store the numbers you see as keys and the value as true. Then loop through each object and check to see if the values are in the other one. If they aren’t then you push them to an array. The advantage of a Javascript object is that lookups are O(1)!

var obj1 = { 4: true, 1: true 3: true}, var obj2 = { 2: true, 3: true, 4:true } -> for…in… -> array.push(2), array.push(1)

Javascript has some functions with “hidden” O(n) value. Hidden just meaning that you might not think they scale in time complexity, but they do. One example is Array.slice(), another is Array.indexOf() that carry O(n) time complexity. So if you’re searching for a value inside of a loop, it’s O(n^2)

1 Like
4

Pretty cool solution. I went a different route and used Sets. Converting the arguments to sets has the advantage of automatically removing duplicate values. Here is my code:

function sym(args) {
  var setA = new Set();
  var setB = new Set();
  
  function checkIfHas(element) {
    if (setA.has(element)) {
      setA.delete(element);
    } else {
      setA.add(element);
    }
  }
  
  for (var i = 0; i < arguments.length; i++) {
    setB = new Set(arguments[i]).forEach(checkIfHas);
  }
  
  return Array.from(setA);
}
1 Like
5 
function diffArray(arr1, arr2) {
  var newArr = [];
  var store1=[],store2=[];
  for(var i=0;i<arr1.length;i++)
    {
      for(var j=0;j<arr2.length;j++)
        {
          if(arr1[i]===arr2[j])
            {
              delete arr1[i];
              delete arr2[j];
            }
        }
    }
  
  newArr=arr1.filter(function(val){
    return val!==null;
  });
  var newArr1=arr2.filter(function(val){
    return val!==null;
  });
  newArr=newArr.concat(newArr1);
  return newArr;
}

diffArray(  [1, 2, 3, 5], [1, 2, 3, 4, 5]  );