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

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;
}