get difference between two arrays (including duplicates)

Question

I see a lot of posts about how to get the difference and symmetric difference of an array in javascript, but I haven't found anything on how to find the difference, including duplicates.

For example:

let original = [1];
let updated = [1, 1, 2];

difference(updated, original);
// Expect: [1, 2]

Is there an elegant way to do this? I'm open to solutions using plain javascript or lodash.

Thanks!

UPDATE

To clarify, an infinite number of duplicates should be supported. Another example:

let original = [1, 1];
let updated = [1, 1, 1, 1, 1, 2];

difference(updated, original);
// Expect: [1, 1, 1, 2]

UPDATE 2

I realized that there may be some confusion on the original requirements. It is true that infinite duplicates should be supported, but the order should not affect the output.

Example:

let original = [1, 1, 2];
let updated = [1, 2, 1, 1, 1];

difference(updated, original);
// Expect: [1, 1]

Answer 1

I would suggest this solution, which avoids a time complexity of O(n²):

function difference(a, b) {
    return [...b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) - 1),
            a.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ) 
    )].reduce( (acc, [v, count]) => acc.concat(Array(Math.abs(count)).fill(v)), [] );
}

let original = [1, 1];
let updated = [1, 1, 1, 1, 1, 2];
let res = difference(updated, original);

console.log(res);

Explanation

This solution creates a Map with a key for every distinct value of the first array (a), and as value the count of occurrences of each. Then b is added to that Map in the same way, except that the count of occurrences counts negative. If that count ends up being zero, then of course this key should not end up in the final result. In fact, the number of occurrences in the final result is the absolute value of the count in the Map for each of its keys.

Details

The code starts with:

new Map()

It is the initial value of the accumulator of the inner reduce. That reduce iterates over a and updates the count of the corresponding key in the Map. The final result of this reduce is thus a Map.

This Map then becomes the initial accumulator value for the outer reduce. That reduce iterates over b and decreases the count in the Map.

This updated Map is spread into an array with the spread operator. This array consists of 2-element sub-arrays, which are key/value pairs. Note that the value in this case is a count which could be positive, zero or negative.

This array is then iterated with the final reduce. Each count is used to create an array of that many elements (in absolute value) of the corresponding value. All this is concatenated to one array, being the return value of the function.

Follow-up Question

In comments you explained you actually needed something different, where the role of both arrays is not the same. The first array should be returned, but with the elements from the second array removed from it.

You could use this code for that:

function difference2(a, b) {
    return a.filter(function(v) {
        return !this.get(v) || !this.set(v, this.get(v) - 1);
    }, b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ));
}

let original = [1, 1, 2];
let updated = [1, 1];
let res = difference2(original, updated);

console.log(res);

Answer 2

function count(n,arr) {
  return arr.filter(a=>a==n).length
}

function diffBetween(arr,arr2) {
  diff = [];
  new Set(arr.concat(arr2)).forEach(
  a => {
    for(x=0;x<Math.abs(count(a,arr)-count(a,arr2));x++)
      diff.push(a)
    }
  );
  return diff;
}

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

How does this work for you?

EDIT:

function difference(a, b) { // trincot's code
    return [...b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) - 1),
            a.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ) 
    )].reduce( (acc, [v, count]) => acc.concat(Array(Math.abs(count)).fill(v)), [] );
}

function count(n,arr) { // My code
  return arr.filter(a=>a==n).length
}

function diffBetween(arr,arr2) { // My code
  diff = [];
  new Set(arr.concat(arr2)).forEach(
  a => {
    for(x=0;x<Math.abs(count(a,arr)-count(a,arr2));x++)
      diff.push(a)
    }
  );
  return diff;
}

in1 = [1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2];
in2 = [1,2,3,4,5,6,1,2,3,4,5,6,7,1,1,1,1,1,1,2,2,2,2,2,2,2];

start = (new Date).getTime();
a = difference(in1,in2);
end = (new Date).getTime();
console.log("trincot done",end-start,"msec");
start = (new Date).getTime();
a = diffBetween(in1,in2);
end = (new Date).getTime();
console.log("stardust done",end-start,"msec");

@trincot's solution above is consistently faster in my testing, so his is clearly superior with large enough datasets.

Answer 3

So, I'd:

• Iterate the updated array, for each element check if it's present on original array, if it's present I remove it from original array (note: in the function below I copy the original object, so I don't affect it), else I push the element to the differences array. At the end, I return the differences array.

---

This code is made to work on various browsers, thus I didn't use Array().indexOf and other newer methods of ECMAScript.

function difference(updated, original) {
  var i, l;
  /* copy original array */
  var degradation = [];
  for (var i = 0, ol = original.length; i < ol; ++i)
    degradation[i] = original[i]

  var diff = [];
  for (i = 0, l = Math.max(updated.length, ol); i < l; ++i) {
    var upd = updated[i];
    var index;
    var b, found;
    /* find updated item in degradation */
    for (b = 0, found = false; b < ol; ++b) {
      if (degradation[b] === upd) {
        /* remove item from degradation */
        delete degradation[b];
        found = true;
        break;
      }
    }
    if (!found)
      diff.push(upd);
  }
  return diff;
}

Answer 4

    Array.prototype.Diff = function( secondArray ) {
    var mergedArray = this.concat( secondArray );
    var mergedString = mergedArray.toString();
    var finalArray = new Array();

    for( var i = 0; i < mergedArray.length; i++ ) {
        if(mergedString.match(mergedArray[i])) {
            finalArray.push(mergedArray[i]);
            mergedString = mergedString.replace(new RegExp(mergedArray[i], "g"), "");
        }
    }
    return finalArray;
}

var let = [ 1 ];
var updated = [ 1, 1, 2 ];

console.log(let.Diff(updated));

I like the prototype way. You can save the prototype function above in a JS file and import in any page that you want, the it's possible to use as an embedded function to the object (Array for this case).

Answer 5

You might do as follows;

var original = [1, 1, 1, 1, 2],
     updated = [1, 2, 1, 1, 3],
      result = (...a) => { var [shorter,longer] = [a[0],a[1]].sort((a,b) => a.length - b.length),
                                              s = shorter.slice();
                           return shorter.reduce((p,c) => { var fil = p.indexOf(c),
                                                                fis = s.indexOf(c);
                                                            fil !== -1 && (p.splice(fil,1),s.splice(fis,1));
                                                            return p;
                                                          },longer).concat(s);
                         };
console.log(result(updated,original));

Answer 6

You can do it the following steps (O(n)).

Let a and b are two arrays

Step 1. create map hash_map of array a value as key and number occurrences of this key as value.

Step 2. push all the elements of array b in result which are not in a using hash_map.

Step 3. push all the elements of array a in result which are not in b using hash_map.

Here is complete code

function diff(a, b) {
    //Step 1 starts here
 var hash_map = a.reduce(function(map, key) {
  map[key] = map[key] ? (map[key]+1) : 1;
  return map;
 }, {});
    //Step 1 ends here
    //Step 2 starts here
 var result = b.filter(function(val) {
  if(hash_map[val]) {
   hash_map[val] = hash_map[val]-1;
   return false;
  }
  return true;
 });
    //Step 2 ends hers
    //Step 3 starts here
 Object.keys(hash_map).forEach(function(key) {
  while (hash_map[key]) {
   result.push(key);
   hash_map[key] = hash_map[key]-1;
  }
 });
    //Step 3 ends here
 return result;
}

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