JS - Merge arrays that share at least one common value

Question

If I have the following array of arrays:

var myArr = [[0, 1, 2], [1, 2, 6], [9, 10], [10, 11], [11, 12], [13]];

How can I merge the arrays that share at least one common value to produce the following output?

var myMergedArr = [[0, 1, 2, 6], [9, 10, 11, 12], [13]];

Thanks!

NOTE: They won't always be nicely ordered and the shared values may not always be the starting/ending values when everything is ordered. I have ordered the above values for clarity.

Answer 1

The array can be reduced with an empty array (merged) as the starting value. For each array in myArray, existing is defined as an array of subArrays of merged such that the intersection of each subArray and array is not empty.

If no such array could be found, existing will remain undefined and a new array (contained in another array) is being defined as existing and pushed to merged.

If multiple matches are found (existing.slice(1) is not empty), they need to be merged together: existing[0] acts as the container where all the other sub-arrays (existing[1..]) get merged (without duplicates). Then those further matches need to be found in merged and removed, as they have been merged already. This guarantees multiple arrays to be merged if they belong together, even if they weren’t merged earlier.

Then, each item of array is pushed to existing[0] if it isn’t included yet. Finally, merged is returned. Then the next iteration of reduce can take merged again as the first argument and continue with the next array in myArr.

This is the ES6 code for that. You can transpile and polyfill it to ES5, if you need to.

var myArr = [
    [0, 1, 2],
    [1, 2, 6],
    [9, 10],
    [10, 11],
    [11, 12],
    [13]
  ],
  myMergedArr = myArr.reduce((merged, array) => {
    let existing = merged.filter((subArray) => subArray.filter((subItem) => array.includes(subItem)).length);

    if (!existing.length) {
      existing = [
        []
      ];
      merged.push(existing[0]);
    }
    else {
      existing.slice(1).forEach((furtherArray) => {
        furtherArray.forEach((item) => {
          if (!existing[0].includes(item)) {
            existing[0].push(item);
          }
        });
        merged.splice(merged.findIndex((subArray) => furtherArray == subArray), 1);
      });
    }

    array.forEach((item) => {
      if (!existing[0].includes(item)) {
        existing[0].push(item);
      }
    });

    return merged;
  }, []);

console.log(myMergedArr);

---

This second snippet is the same code but with a changed array. This is to demonstrate that this script will work, even if the sub-arrays aren’t in order: first [0, 1, 2] is on its own, then [3, 4, 5] is also on its own — both still separated. Only later [2, 3] causes all previous arrays to merge into one.

var myArr = [
    [0, 1, 2],
    [3, 4, 5],
    [2, 3],
    [7, 9],
    [9, 10],
    [13]
  ],
  myMergedArr = myArr.reduce((merged, array) => {
    let existing = merged.filter((subArray) => subArray.filter((subItem) => array.includes(subItem)).length);

    if (!existing.length) {
      existing = [
        []
      ];
      merged.push(existing[0]);
    }
    else {
      existing.slice(1).forEach((furtherArray) => {
        furtherArray.forEach((item) => {
          if (!existing[0].includes(item)) {
            existing[0].push(item);
          }
        });
        merged.splice(merged.findIndex((subArray) => furtherArray == subArray), 1);
      });
    }

    array.forEach((item) => {
      if (!existing[0].includes(item)) {
        existing[0].push(item);
      }
    });

    return merged;
  }, []);

console.log(myMergedArr);

Answer 2

I believe the problem can be solved with a fairly simple functional piece of code as follows;

function merger(arr){
  return arr.map((e,i,a) => a.slice(i)
                             .reduce((p,c) => e.some(n => c.includes(n)) ? [...new Set([...p,...c])] : p,[]))
            .reduce((r,s) => { var merged = false;
                               r = r.map(a => a.some(n => s.includes(n)) ? (merged = true, [...new Set([...a,...s])]) : a);
                               !merged && r.push(s);
                               return r;
                             },[]);
}

var arr1 = [[0, 1, 2], [1, 2, 6], [9, 10], [10, 11], [11, 12], [13]],
    arr2 = [[0, 1], [2, 3], [1, 2]];


console.log(merger(arr1));
console.log(merger(arr2));

A little explanation on the critical part. Using Set object hand to hand with Array object is very easy with the help of spread operator. So the following piece might look a little confusing but it does an important job.

[...new Set([...a,...s])]

Let's assume a is an array or set and s is another array or set. Then [...a,...s] makes an array of the two merged into. new Set([...a,...s]) makes a new set by removing the dupes in the merged array. [...new Set([...a,...s])] turns our set back into an array of a and b concatenated and dupes removed. Cool..!

a.some(n => s.includes(n))

If array a and array s have at least one common item returns true else false.

Answer 3

A disjoint-set data structure seems perfect for your case:

function merge(arrays) {
  var ds = new DisjointSet();
  arrays.forEach(function(array) {
    array.reduce(function(prevSet, currentValue) {
      var currentSet = ds.getSet(currentValue);
      if(prevSet) prevSet.mergeWith(currentSet);
      return currentSet;
    }, false);
  });
  return ds.partitions();
}
var myArr = [[0, 1, 2], [1, 2, 6], [9, 10], [10, 11], [11, 12], [13]];
console.log(JSON.stringify(merge(myArr)));

<script> /* DisjointSet library */
class MySet {
  constructor(owner) {
    this.rank = 0;
    this.parent = this;
    this.owner = owner;
  }
  representative() {
    var parent = this.parent;
    if(this === parent) return this;
    while(parent !== (parent = parent.parent));
    this.parent = parent; /* Path compression */
    return parent;
  }
  mergeWith(other) {
    var r1 = this.representative(),
        r2 = other.representative();
    if(r1 === r2) return;
    if(r1.owner !== r2.owner) throw new Error("Can't merge");
    if(r1.rank > r2.rank) { r2.parent = r1; return; }
    r1.parent = r2;
    if(r1.rank === r2.rank) ++r1.rank;
  }
}
class DisjointSet {
  constructor() {
    this.sets = new Map();
  }
  getSet(value) {
    var sets = this.sets;
    var set = sets.get(value);
    if(set) return set;
    set = new MySet(this);
    sets.set(value, set);
    return set;
  }
  partitions() {
    var parts = new Map();
    for(var [value,set] of this.sets) {
      var repre = set.representative();
      var arr = parts.get(repre);
      if(arr) arr.push(value);
      else parts.set(repre, [value]);
    }
    return [...parts.values()];
  }
}
</script>

Assuming constant map operations, the amortized time cost should be only O(n α(n)) ≈ O(n).

the amortized time per operation is only O(α(n)), where α(n) [...] is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

Note I used ES6 maps to be able to associate each value with its set. This is not needed if all values are numbers, you could then store them as object properties. But in partitions you will need to extract the value associated with a set, and storing that data will require more memory.

function merge(arrays) {
  var ds = new DisjointSet();
  arrays.forEach(function(array) {
    array.reduce(function(prevSet, currentValue) {
      var currentSet = ds.getSet(currentValue);
      if(prevSet) prevSet.mergeWith(currentSet);
      return currentSet;
    }, false);
  });
  return ds.partitions();
}
var myArr = [[0, 1, 2], [1, 2, 6], [9, 10], [10, 11], [11, 12], [13]];
console.log(JSON.stringify(merge(myArr)));

<script> /* DisjointSet library */
function MySet(value, owner) {
  this.rank = 0;
  this.parent = this;
  this.value = value;
  this.owner = owner;
}
MySet.prototype.representative = function() {
  var parent = this.parent;
  if(this === parent) return this;
  while(parent !== (parent = parent.parent));
  this.parent = parent; /* Path compression */
  return parent;
};
MySet.prototype.mergeWith = function(other) {
  var r1 = this.representative(),
      r2 = other.representative();
  if(r1 === r2) return;
  if(r1.owner !== r2.owner) throw new Error("Can't merge");
  if(r1.rank > r2.rank) { r2.parent = r1; return; }
  r1.parent = r2;
  if(r1.rank === r2.rank) ++r1.rank;
};
function DisjointSet() {
  this.sets = Object.create(null);
}
DisjointSet.prototype.getSet = function(value) {
  var sets = this.sets;
  var set = sets[value];
  if(set) return set;
  set = new MySet(value, this);
  sets[value] = set;
  return set;
};
DisjointSet.prototype.partitions = function() {
  var parts = [];
  var assoc = Object.create(null);
  var sets = this.sets;
  Object.getOwnPropertyNames(sets).forEach(function(value) {
    var set = sets[value];
    var repreValue = set.representative().value;
    var arr = assoc[repreValue];
    if(arr) arr.push(set.value);
    else parts.push(assoc[repreValue] = [set.value]);
  });
  return parts;
};
</script>