Published: Dec 20, 2022

## Problem Description

There are

`n`

people in a social group labeled from`0`

to`n - 1`

. You are given an array logs where`logs[i] = [timestamp[i], x[i], y[i]]`

indicates that`x[i]`

and`y[i]`

will be friends at the time`timestamp[i]`

.Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.

Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.

Constraints:

`2 <= n <= 100`

`1 <= logs.length <= 10**4`

`logs[i].length == 3`

`0 <= timestampi <= 10**9`

`0 <= x[i], y[i] <= n - 1`

`x[i] != y[i]`

- All the values
`timestamp[i]`

are unique.- All the pairs
`(x[i], y[i])`

occur at most one time in the input.https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

## Examples

```
Example 1
Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],
[20190312,1,2],[20190322,4,5]]
n = 6
Output: 20190301
Explanation:
20190101: [0, 1], [2], [3], [4], [5]
20190104: [0, 1], [2], [3, 4], [5]
20190107: [0, 1], [2, 3, 4], [5]
20190211: [0, 1, 5], [2, 3, 4]
20190224: [0, 1, 5], [2, 3, 4]
20190301: [0, 1, 5, 2, 3, 4]
```

```
Example 2
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
```

## How to Solve

It’s not difficult to think of the union-find approach for this problem. At the beginning, n groups are there. As time goes by, groups are merged and merged. Eventually, a single group will be formed. This is exactly the union-find does.

Ths solution here starts from sorting the given logs by the timestamp. After that, the solution uses a typical union-find approach. When the number of groups becomes 1, the answer is there.

## Solution

```
class TheEarliestMomentWhenEveryoneBecomeFriends {
private:
vector<int> groups;
public:
int _find(int a) {
while (a != groups[a]) {
a = groups[a];
}
return a;
}
int _union(int a, int b, int n) {
int ga = _find(a);
int gb = _find(b);
if (ga != gb) {
groups[ga] = gb;
n -= 1;
}
return n;
}
int earliestAcq(vector<vector<int>>& logs, int n) {
for (auto i = 0; i < n; ++i) {
groups.push_back(i);
}
sort(logs.begin(), logs.end(), [](const auto &a, const auto &b) {return a[0] < b[0]; });
for (vector<int> log : logs) {
int t = log[0], a = log[1], b = log[2];
n = _union(a, b, n);
if (n == 1) { return t; }
}
return -1;
}
};
```

```
```

```
```

```
class TheEarliestMomentWhenEveryoneBecomeFriends:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
groups = [i for i in range(n)]
def find(a):
while a != groups[a]:
a = groups[a]
return a
def union(a, b, n):
ga, gb = find(a), find(b)
if ga != gb:
groups[ga] = gb
n -= 1
return n
for t, a, b in sorted(logs, key=lambda x: x[0]):
n = union(a, b, n)
if n == 1:
return t
return -1
```

```
```

## Complexities

- Time:
`O(log(n))`

- Space:
`O(n)`