The Earliest Moment When Everyone Become Friends

Hard
0/120
Average time to solve is 45m
profile
Contributed by
15 upvotes
Asked in companies
AdobeIBMMAQ Software

Problem statement

In a social group, there are ‘N’ people, with unique integer ids from 0 to (N - 1). We have an array of ‘logs’, where each logs[i] = [timestamp, idA, idB] contains a non-negative integer ‘timestamp’ and the ‘ids’ of two different people.

Each log represents the time in which two different people became friends.

Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B. Your task is to return the earliest time every person became acquainted with every other person.

Note:

1) The ids are 0-indexed.

2) Friendship is symmetric here. That is, if A is friends with B, then B is friends with A.

3) Return -1 if there is no such earliest time.

For example:

Given ‘logs’ =[[2, 0, 1],[3, 1, 2],[4, 2, 3]].

The answer here would be 4 : 
When the people with id 2 and 3 become friends, then the circle gets completed, and the time among them is 4, and because 4 is the largest time among all, the time for the circle to get completed is 4.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two integers, ‘N’, representing the number of ‘ids’ people, and ‘M’ which denotes the number of ‘logs’.

The following ‘M’ lines of each test case contain exactly three integers, denoting the 'time', 'idA', and 'idB'.

Output format:

For each test case, print a single line containing a single integer denoting the minimum time for the connection to get complete. 

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything. It's been already taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 150
1 <= M <= 300

Where ‘T’ is the number of test-cases and, ‘N’ is the number of people, and ‘M’ is the number of logs.

Time limit: 1 second

Sample Input 1 :

2
4 3
2 0 1
3 1 2
4 2 3
4 2
2 0 1
3 1 2

Sample Output 1:

4
-1

Explanation of the Sample Input 1:

For the first test case:
The answer here would be 4 : 
When the people with id 2 and 3 become friends, then the circle gets completed, and the time among them is 4, and because 4 is the largest time among all, the time for the circle to get completed is 4.


For the second test case:
The answer will be -1 : 
This is because there is no possible way such that the circle get completed because there no connection of the person with ‘id’ = 3.

Sample Input 2 :

2
4 4
2 0 1
3 1 2
1 2 3
1 0 3
4 3
2 0 1
1 1 2
1 2 3

Sample Output 2 :

2
2
Hint

Can you use DSU to find when two groups become friends?

Approaches (1)
DSU

The main idea is to sort the logs in increasing order of the time between the two ids.

Then use DSU to make a connection and find the connected component. 

 

The main idea is to use a DSU data structure to find connected components. A DSU data structure can be used to maintain knowledge of the connected components of a graph and query for them quickly. In particular, we would like to support two operations:

  1. find(node x), which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component, and:
  2. union(node x, node y), which draws an edge (x, y) in the graph, connecting the components with id find(x) and find(y) together.

 

The moment we get the full circle, we can return that time.

  • Sort the ‘logs’ array in increasing order based on the ‘time’ variable.
    • This can be done by passing a comparator that compares vectors a and b and return the bool value of a[0] < b[0].
  • We will maintain a variable ‘circle’ which tells us how much of the connected component has formed. Initially, circle = ‘N.’
  • Traverse the logs and make connections between the two ids if they have a different parent. We can find the parents of the current node by using the helper function ‘findParent.’
    • findParent take two inputs:
      • The node, for which we need to find parent
      • The parent array, which stores the parent of all nodes.
    • If the parent[i] = i , then we return i .
  • If they have different parents, we will union them, using the function ‘unionIt and reduce the circle by 1.
  • Union It works in the following way :
    • It takes three input :
      • Node1
      • Node2
      • The parent array, which stores the parent of all nodes.
    • It assigns parent[node2] = node1
  • The state when we get circle = 1. We return the time because that is the moment the circle gets complete, and hence we get the maximum time.
Time Complexity

O(M * log(M)), where 'M' is the size of the array ‘LOGS’.

 

Since we are sorting the logs array, the net time complexity will be O(M * log(M)).

Space Complexity

O(N), where ‘N’ is the number of nodes.

 

Since we are keeping track of the parent nodes, which is equal to the ‘parent’ array’s size, hence space complexity: O(N).

Code Solution
(100% EXP penalty)
The Earliest Moment When Everyone Become Friends
Full screen
Console