Diff an array of objects so that it matches another without recreating any valid objects

Question

Let's say I have 2 arrays each of which holds a few different objects

class Object1 {}
class Object2 {}
class Object3 {}
class Object4 {}
class Object5 {}
class Object6 {}

const arrayA = [
  new Object1(), 
  new Object2(), 
  new Object3()
]
const arrayB = [
  new Object4(), 
  new Object1(), 
  new Object2(), 
  new Object6()
]

I need to mutate arrayB so that it holds instances of the same classes as arrayA in the same order.

But I need to reuse any instances in arrayB of classes that are also present in arrayA.

The desired output here would be:

  arrayB = [
    instanceOfObject1AlreadyInArrayB,
    instanceOfObject2AlreadyInArrayB,
    new Object3()
  ]

How would you solve this with the best possible big O notation?

Are there any comparable algorithm names I can research?

Answer 1

One approach here is to copy arrayB into a Map from each element's constructor to its value. Then we can iterate over arrayA's elements and for each one, if its constructor is a key in the Map we use the existing value, otherwise we construct a new instance.

The time complexity of this is essentially just O(a+b) where a is the length of arrayA and b is the length of arrayB, assuming that operations on a Map are constant-time O(1). Technically the spec only requires that it be sublinear, so then all we can say for sure is that the time complexity of the whole process is strictly less than O((a+b)²), so at the least it scales better than iterating arrayB for each element of arrayA (e.g., arrayA.map(a => arrayB.find(⋯)) , which would be O(a×b).

And because apparently you want arrayB to be mutated, we can clear arrayB after copying its contents to the Map, and then just push the elements onto it. This is O(a) and thus doesn't affect the overall time complexity.

Here is an example:

// not necessary, just adding a common constructor so that we can
// see exactly when new instances are being constructed
class Parent {
  constructor() {
    console.log("constructed " + this.constructor.name)
  }
}
class Object1 extends Parent { }
class Object2 extends Parent { }
class Object3 extends Parent { }
class Object4 extends Parent { }
class Object5 extends Parent { }
class Object6 extends Parent { }

console.log("making arrayA")
const arrayA = [
  new Object1(),
  new Object2(),
  new Object3()
]
console.log("making arrayB")
const arrayB = [
  new Object4(),
  new Object1(),
  new Object2(),
  new Object6()
]

const map = new Map();
arrayB.forEach(v => map.set(v.constructor, v));
arrayB.length = 0;
console.log("recreating arrayB contents")
arrayA.forEach(v => arrayB.push(map.get(v.constructor) ?? new v.constructor()));

console.log(JSON.stringify(arrayB.map(x => x.constructor.name)))

If you run that snippet you'll see that arrayB ends up with instances of Object1, Object2, and Object3 in that order, but only the Object3 constructor gets invoked; the Object1 and Object2 instances from arrayB are re-used.

Answer 2

Identify the classes present in arrayA that are not in arrayB. Using the filter() on arrayA, check if each class is included in arrayB, if not, add it to a new array and create new instances of these classes and add them to arrayB. Add variable missingClasses, this contains the classes that are in arrayA but not in arrayB, and use it to create the new instances. Then, make sure that the objects in arrayB are in the same order as in arrayA.

const classesInA = arrayA.map(obj => obj.constructor);
const classesInB = arrayB.map(obj => obj.constructor);
const missingClasses = classesInA.filter(cls => !classesInB.includes(cls));

const newInstances = missingClasses.map(cls => new cls());

// Remove objects from arrayB that are not in arrayA
arrayB = arrayB.filter(obj => classesInA.includes(obj.constructor));

const sortedArrayB = arrayB.concat(newInstances).sort((a, b) => {
 return classesInA.indexOf(a.constructor) - classesInA.indexOf(b.constructor);
});