Photo by Chang Duong on Unsplash

The Earliest Moment When Everyone Become Friends in C# and Typescript

LeetCode problem link :

The Earliest Moment When Everyone Become Friends - LeetCode

Intuition

The intuition is to somehow link all the people who are becoming friends and associate them as a single uniform group. So, whenever we detect a new friend, we add it to the existing single structure if it is not already a part of it.

Approach

The algorithm we are using here is called Union-Find algorithm. The Union-Find algorithm, also known as the Disjoint-Set data structure, is a data structure and algorithm used to efficiently track and merge disjoint sets. It provides operations to create sets, determine which set an element belongs to, and merge sets together.

The Union-Find algorithm is commonly used in graph algorithms, such as Kruskal’s algorithm for finding a minimum spanning tree or detecting cycles in a graph. It maintains a collection of disjoint sets and provides two main operations:

1. Union: Merge two sets together. It takes two elements from different sets and merges their respective sets into a single set.
2. Find: Determine the set to which an element belongs. It returns a representative element of the set to which the input element belongs.

The Union-Find algorithm utilizes an array or a tree-like structure to represent the sets. Each element in the structure points to its parent element, with the root of each set pointing to itself. The algorithm optimizes the performance by utilizing path compression and union by rank.

Path compression optimizes the Find operation by making each element point directly to the root of its set, reducing future lookups. Union by rank optimizes the Union operation by merging smaller sets into larger sets, which helps maintain a balanced structure and prevents performance degradation.

Here is a high-level outline of the Union-Find algorithm:

1. Initialize the data structure with individual elements considered as separate sets.
2. For each Union operation, find the root of each element and merge the sets by making one root the parent of the other.
3. For each Find operation, find the root of the given element and return it as the representative element of the set.

By utilizing the Union-Find algorithm, you can efficiently manage disjoint sets and perform operations such as merging sets and finding the set to which an element belongs.

Code in C# and Typescript

public class DisjointSets
{
    int[] parents;
    int[] weights;

    public DisjointSets(int n)
    {
       parents = new int[n];
       weights = new int[n];

       for(int i = 0 ;  i < n ; i++)
       {
           parents[i] = i;
           weights[i] = i;
       }
    }

    public void Union(int a,int b)
    {
       int rootA = Find(a);
       int rootB = Find(b);

       if(weights[rootA] > weights[rootB])
       {
          parents[rootB] = rootA;
          weights[rootA] += weights[rootB];
       }
       else
       {
          parents[rootA] = rootB;
          weights[rootB] += weights[rootA];
       }
    }

    public int Find(int a)
    {
        while( a != parents[a])
        {
            a = parents[parents[a]];
        }
        return a;
    }
}




public class Solution {
    public int EarliestAcq(int[][] logs, int n) 
    {
        DisjointSets set = new DisjointSets(n);

        Array.Sort(logs,((a,b) => {return a[0]-b[0] < 0 ? -1 : 1;}));

        int earliestTimestampWhenAllBecameFriends = 0;

        for(int i = 0 ; i < logs.Length ; i++)
        {
           int timestamp = logs[i][0];
           int a = logs[i][1];
           int b = logs[i][2];

           if(set.Find(a) != set.Find(b))
           {
               earliestTimestampWhenAllBecameFriends = timestamp;
               set.Union(a,b);
           }
        }
        
        // Code to check if at the end every person has become friends with the rest of the people.
        int parent = set.Find(0);
        for(int i = 0 ; i < n ; i++)
        {
            if(parent != set.Find(i))          
            {
              return -1;
            }
        }
        return earliestTimestampWhenAllBecameFriends;
     }
}

function earliestAcq(logs: number[][], n: number): number 
{
   const set = new DisjointSets(n);

    logs.sort((a, b) => a[0] - b[0]);

    let earliestTimestampWhenAllBecameFriends = 0;

    for (let i = 0; i < logs.length; i++) {
      const timestamp = logs[i][0];
      const a = logs[i][1];
      const b = logs[i][2];

      if (set.Find(a) !== set.Find(b)) {
        earliestTimestampWhenAllBecameFriends = timestamp;
        set.Union(a, b);
      }
    }

    // Code to check if at the end every person has become friends with the rest of the people.
    let parent = set.Find(0);
    for (let i = 0; i < n; i++) {
      if (parent !== set.Find(i)) {
        return -1;
      }
    }
    return earliestTimestampWhenAllBecameFriends;
};
class DisjointSets {
  parents: number[];
  weights: number[];

  constructor(n: number) {
    this.parents = new Array(n);
    this.weights = new Array(n);

    for (let i = 0; i < n; i++) {
      this.parents[i] = i;
      this.weights[i] = i;
    }
  }

  Union(a: number, b: number) {
    let rootA = this.Find(a);
    let rootB = this.Find(b);

    if (this.weights[rootA] > this.weights[rootB]) {
      this.parents[rootB] = rootA;
      this.weights[rootA] += this.weights[rootB];
    } else {
      this.parents[rootA] = rootB;
      this.weights[rootB] += this.weights[rootA];
    }
  }

  Find(a: number): number {
    while (a !== this.parents[a]) {
      a = this.parents[this.parents[a]];
    }
    return a;
  }
}