Skip to content

Instantly share code, notes, and snippets.

@manderly
Created August 1, 2021 16:58
Show Gist options
  • Save manderly/8131b6818db11f8dc38dc1e1c8396a09 to your computer and use it in GitHub Desktop.
Save manderly/8131b6818db11f8dc38dc1e1c8396a09 to your computer and use it in GitHub Desktop.
Leetcode 1101 The Earliest Moment When Everyone Become Friends
function earliestAcq(logs: number[][], n: number): number {
logs.sort((a:number[], b:number[]) => {
return (a[0] - b[0]);
});
let mapOfSets = new Map();
// put every friend ID into its own individual set - O(n)
for (let i = 0; i < n; i++) {
let individualSet = new Set();
individualSet.add(i);
mapOfSets.set(i, individualSet);
}
// now every friend is its own set in the map
console.log(mapOfSets);
// step through the logs and join the sets as matches are encountered
for (let i = 0; i < logs.length; i++) {
let friendA = logs[i][1];
let friendB = logs[i][2];
let setA = mapOfSets.get(friendA);
let setB = mapOfSets.get(friendB);
if (setA != setB) {
// join the two sets
for (let friend of setB) {
// add all the friends from setB to setA
setA.add(friend);
// update map of sets such that setA is pointed at by each friend originally from B
mapOfSets.set(friend, setA);
}
if (setA.size === n) {
// every friend is now accounted for in set A
// return the timestamp where this was achieved
return logs[i][0];
}
}
}
return -1;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment