CODEWITHSUNDEEP
javascriptarrays
Youssef Z
Youssef Z

Reputation: 13

For two arrays find items that are present in one array only (symmetric difference)

I need to compare two arrays and return a new array with any items only found in one of the two given arrays, but not both. In other words, return the symmetric difference of the two arrays. My algorithm consists of using the map() method on the first array and compare each of element of that array with the elements of the second array using every(). If this method returns true, the element gets returned on the block level of map (which will eventually add it to the returned array) if not it's discarded. I'm not sure why my code is not working. This is an example of a wrong output using my code:

function diffArray(arr1, arr2) {
    var newArr = arr1
        .map(elem1 => {
            if (arr2.every(elem2 => elem2 != elem1)) {
                return elem1;
            }
        });
    return newArr;
}

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

This is the wrong output: [ undefined, undefined, undefined, undefined ]

The expected output is : [4]

Upvotes: 1

Views: 1182

Answers (4)

Yevhen Horbunkov
Yevhen Horbunkov

Reputation: 15540

Your function returns elements of the first array that are not present in the second array.

Its return is explained by the fact that .map() returns the array of exact same size as your input (arr1), but since all items of arr1 are present in arr2 you don't enter if(-statement body hence undefined is getting returned.

If your intention was to return items that are present in one array only (regardless of the order they're passed in), you may leverage the Map object together with Array.prototype.reduce():

  • combine arrays-arguments into common array of arrays
  • loop through those inner arrays with .reduce(), building up the Map, showing how many times each item is seen within combined array
  • for each item of combined array remove duplicates and increment respective counter
  • spread resulting Map into .entries() and .filter() those to find out uniques

const arr1 = [1, 2, 3, 5], 
      arr2 = [1, 2, 3, 4, 5],
      
      getUniques = (...arrays) => 
        [...arrays
          .reduce((acc, arr) => {
            [...new Set(arr)]
              .forEach(item => 
                acc.set(item, (acc.get(item)||0)+1))
            return acc
          }, new Map)
          .entries()]
          .reduce((acc, [item, repetitions]) => 
            (repetitions == 1 && acc.push(item), acc), [])
            
console.log(getUniques(arr1, arr2))
.as-console-wrapper {min-height:100%;}

Above approach is of O(n)-time complexity, as opposed to your initial attempt and the answer you have currently accepted (both having O(n²)-time complexity). As a result it may perform much faster on large arrays (arbitrary number of arrays, as a bonus).

Upvotes: 0

Ori Drori
Ori Drori

Reputation: 192287

This algorithm works even when numbers appear multiple times in both arrays.

It uses a Map created from the items of both arrays. The map contains the item as the key, and the value is the amount of times it's found in the 1st array - the number of times it's found it the 2nd array.

After creating the Map, it's converted to an array of [item, count]. The array is then filtered, and all items with a count of 0 are removed (they exist equally in both arrays), and then we map the array to an array of items.

const getCounts = (arr, init = new Map(), inc = 1) =>
  arr.reduce((acc, item) => acc.set(item, (acc.get(item) || 0) + inc), init);

function diffArray(arr1, arr2) {
  // create a Map that adds 1 for all items in arr1, and substructs 1 for every item in arr2
  const counts = getCounts(arr2, getCounts(arr1), -1);
  
  // convert to an array of pairs [item, count]
  return Array.from(counts)
    .filter(([, v]) => v) // remove all items with count 0
    .map(([k]) => k); // map to the original item
}

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

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386680

Your approach iterates the first array and because of using map along with the check for the value, you get undefined for every element of arr1.

If you take filter and the other array as well, you could get the wanted result.

function diffArray(arr1, arr2) {
    return [
        ...arr1.filter(elem1 => arr2.every(elem2 => elem2 != elem1)),
        ...arr2.filter(elem1 => arr1.every(elem2 => elem2 != elem1))
    ];
}

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

Another approach takes an array of all values of both arrays and filter by checking if the value is not included in both arrays.

function diffArray(arr1, arr2) {
    return [...arr1, ...arr2].filter(v => arr1.includes(v) !== arr2.includes(v));
}

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

Upvotes: 1

Robert
Robert

Reputation: 2763

Use _.difference(array, [values])

from lodash

or

own solution :

const diffArray = (arrayA, arrayB) => {
    const output = []
    const setA = new Set(arrayA);
    arrayB.forEach((n) =>{
       if(!setA.has(n)){
         output.push(n)
       }
    })
    const setB = new Set(arrayB);
    arrayA.forEach(n =>{
       if(!setB.has(n)){
         output.push(n)
       }
    })
    return output;
}

console.log(diffArray([1, 2, 3, 5, 6], [1, 2, 3, 4, 5])); //4, 6

Upvotes: 0

Related Questions