The Earliest Moment When Everyone Becomes Friends

Soumya Agrawal
Last Updated: May 13, 2022

 

Introduction

 

You might have listened about the disjoint sets in mathematics where the intersection of two sets results in a null value. In our programming world, disjoint sets or merge–find set is a data structure that stores a collection of disjoint (non-overlapping) sets. 

 

Disjoint sets are used to detect whether a graph contains the cycle or not, which means it finds the connected components in the graph. Union-Find Algorithm(union by rank and path compression) can be used to check whether an undirected graph has a cycle or not.

 

In this problem, we will be using this concept. Let’s see how and what the problem states.

 

Problem Statement

We are given an array of ‘arr,’ where each arr[i] = [time, idA, idB] has a non-negative integer ‘time’ and the ‘ids’ of two different people. ‘N’ people have unique ids ranging from 0 to N-1.

Each ‘arr’ represented when two different people became friends.

If A is a friend with B, or A is a friend with someone acquainted with B, then we aim to return the earliest time every person became acquainted with every other person.

 

Note:

  • The ids are 0-indexed.

 

  •  Friendship is symmetric here. If A is friends with B, then B is friends with A.

 

We will see this with the help of an example for more clarity.

 

Example1: 

 

Input: N = 4, arr[] = {{2, 0, 1}, {3, 1, 2}, {4, 2, 3}}

Starting id from ‘0’ to ‘N-1’ i.e the number of people are 0,1,2,3.

 

  • At time = 2, {0} and {1} became friends. Group of people become= {0, 1}, {2}, {3}.
  • At time = 3, {1} and {2} became friends. Group of people become= {0, 1, 2}, {3}.
  • At time = 4, {2} and {3} became friends. Group of people become= {0, 1, 2, 3}.

The circle gets completed, and the time is 4 because 4 is the largest time to complete a circle.

Output:

4

Example2:

Input: arr=[[201,0,1],[209,3,4],[207,2,3],[208,1,5],[202,2,4],[203,0,3],[200,1,2],[206,4,5]], 

N = 6

Output: 203

Explanation: 

  • At time = 201,{0} and {1} become friends and group of people become= {0,1}, {2}, {3}, {4}, {5}.
  • At time = 209,{3} and {4} become friends and group of people become= {0,1}, {2}, {3,4}, {5}.
  • At time = 207,{2} and {3} become friends, and group of people become= {0,1}, {2, 3, 4}, {5}.
  • At time = 208,{1} and {5} become friends, and group of people become= {0,1,5}, {2,3,4}.
  • At time = 202,{2}, and {4} are already friend.
  • At time = 203,{0} and {3} have become friends, and that is what we want so that the output will be ‘203’.

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

 

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.

 

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

 

Happy coding!!

 

Was this article helpful ?
0 upvotes