The Earliest Moment When Everyone Becomes Friends

Approach

DSU means to make a connection and find the connected components, and for this, we will be making two functions, i.e., union() and find() and follow the algorithm.

The idea is to perform the union operations between people in order of the increasing value of time. And the moment we get the whole circle, we return the time.

• Sort the ‘arr’ array in increasing order based on the ‘time’ variable using the comparator.
• We will maintain a variable that tells us how much the connected component is formed.
• Traverse the arr and make connections between the two ids if they have a different parent.
• Find() function takes one parameter as input, i.e., the node for which we have to find the parent, and it checks that node in the parent array.
• Union() function takes two parameters as input, i.e., two nodes, and assigns the nodes in the parent array.
• When the count of unions becomes 1, that is the first time all people become friends and output time.

Before jumping into the implementation, give it a shot yourself for the problem The Earliest Moment When Everyone Becomes Friends.

Implementation

class Solution {
      public int earliest(int[][] arr, int N) {
          UF uf= new UF(N);
      
        // Sorting the array
        Arrays.sort(arr, (a, b)-> a[0]-b[0]);
    // Traversing through the array
     for(int [] log : arr){
         if(uf.find(log[1]) != uf.find(log[2])){
                  uf.union(log[1], log[2]);   
             }
             
            // If we found the count of unions as ‘1’ then we have found all the friends.
             if(uf.count == 1){
                 return log[0];
            }
        }
         
         return -1;
    }
 }
 
 class UF{
     int [] parent;
     int [] size;
     int count;
     
     public UF(int n){
         this.parent = new int[n];
         this.size = new int[n];
         for(int i = 0; i<n; i++){
             parent[i] = i;
             size[i] = 1;
        }
         
         this.count = n;
    }
     
    // Find() function to find the unique id.
     public int find(int i){
        while(i != parent[i]){
             parent[i] = parent[parent[i]];
             i = parent[i];
        }
         
         return parent[i];
    }
    
     // Draws an edge in the graph, connecting the components with the id.
     public void union(int p, int q){
         int i = find(p);
        int j = find(q);
         if(size[i] > size[j]){
             parent[j] = i;
             size[i] += size[j];
         }else{
             parent[i] = j;
             size[j] += size[i];
        }
         
         this.count--;
    }
 }

You can also try this code with Online Java Compiler

Run Code

Analysis Of Complexity

Time Complexity: The time complexity is O(n logn) where n is arr.length and find takes O(logn) time.

Space Complexity: O(N)- Auxiliary space.

FAQs

1. What do you mean Union-Find Algorithm?
   Union-find algorithm is used to detect the cycle in the graph using two functions, union() and find().
    
2. What do you mean by an acyclic graph?
   An acyclic graph is a graph with no cycles.
    
3. What is the time complexity to solve this problem?
   The time complexity of this approach is O(nlogn) where n=arr.length.

Key Takeaways

This blog will give you insights into the problem of The Earliest Moment When Everyone Becomes Friends and examples. The approach we have followed for this problem is DSU which means to find the connected components in the graph using Union and Find Algorithm.

DSU is a vital application for various problems of graphs, and one should grasp it appropriately.

Practice this question for more clarity regarding the concept and approach.

Check out the following problems - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.

Don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio. 

Happy coding!!