abagshaw abagshaw - 2 months ago 8
Javascript Question

JS - Merge arrays that share at least one common value

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

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

Comments