What is a more efficient way to check for duplicates in an array of sets

Question

given this input:

const set1 = new Set([10, "someText", {a: 1, b: 2}]);
const set2 = new Set([10, "someText", {a: 1, b: 2}]);
const set3 = new Set([5, "someText", {a: 3, b: 4}]);
const arr = [set1, set2, set3];

combineDupSets(arr);

Wanted result:

[
  Set { 10, 'someText', { a: 1, b: 2 } },
  Set { 5, 'someText', { a: 3, b: 4 } }
]

I am writing a function to eliminate all the duplicate sets, and since Set() won't check for duplicates when it's an object or set itself, I wrote the following:

function combineDupSets(arr) {
  const hold = [];

  arr.forEach(set =>{
    const copySet = [...set];
    const stringify = JSON.stringify(copySet);
    if(hold.indexOf(stringify) === -1) {
      hold.push(stringify)
    }
  })


  const end = hold.map(item => JSON.parse(item));

  const res = end.map(item => item = new Set(item))

  return res;
}

Here, I have to use 3 arrays sized O(n) to check for this, and I was just wondering if there's any other solution that is readable that will be more efficient in checking for this for both time and space complexity?

Thank you

Answer 1

Instead of using indexOf in an array, consider putting the sets onto an object or Map, where the key is the stringified set and the value is the original set. Assuming that the values are in order:

function combineDupSets(arr) {
   const uniques = new Map();
   for (const set of arr) {
      uniques.set(JSON.stringify([...set]), set);
   }
   return [...uniques.values()];
}

This

• iterates over the arr (O(n))
• iterates over each item inside once (total of O(n * m) - there's no getting around that)
• Iterates over the created Map and puts it into an array (O(n))

If the set values aren't necessarily in order - eg, if you have

Set([true, 'foo'])
Set(['foo', true])

that should be considered equal, then it'll get a lot more complicated, since every item in each Set not only has to be iterated over, but also compared against every other item in every other Set somehow. One way to implement this is to sort by the stringified values:

function combineDupSets(arr) {
   const uniques = new Map();
   for (const set of arr) {
      const key = [...set].map(JSON.stringify).sort().join();
      uniques.set(key, set);
   }
   return [...uniques.values()];
}