Welcome to Subscribe On Youtube
1101. The Earliest Moment When Everyone Become Friends
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
.
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: The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5]. The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5]. The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5]. The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4]. The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens. The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.
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.
Constraints:
2 <= n <= 100
1 <= logs.length <= 10^{4}
logs[i].length == 3
0 <= timestamp_{i} <= 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.
Solutions
Solution 1: Sorting + UnionFind
We sort all the logs in ascending order by timestamp, then traverse the sorted logs. Using a unionfind set, we check whether the two people in the current log are already friends. If they are not friends, we merge them into one friend circle, until everyone is in one friend circle, then return the timestamp of the current log.
If we have traversed all the logs and not everyone is in one friend circle, then return $1$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of logs.

class Solution { private int[] p; public int earliestAcq(int[][] logs, int n) { Arrays.sort(logs, (a, b) > a[0]  b[0]); p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } for (int[] log : logs) { int t = log[0], x = log[1], y = log[2]; if (find(x) == find(y)) { continue; } p[find(x)] = find(y); if (n == 1) { return t; } } return 1; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } }

class Solution { public: int earliestAcq(vector<vector<int>>& logs, int n) { sort(logs.begin(), logs.end()); vector<int> p(n); iota(p.begin(), p.end(), 0); function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); }; for (auto& log : logs) { int x = find(log[1]); int y = find(log[2]); if (x != y) { p[x] = y; n; } if (n == 1) { return log[0]; } } return 1; } };

class Solution: def earliestAcq(self, logs: List[List[int]], n: int) > int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(n)) for t, x, y in sorted(logs): if find(x) == find(y): continue p[find(x)] = find(y) n = 1 if n == 1: return t return 1

func earliestAcq(logs [][]int, n int) int { sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] }) p := make([]int, n) for i := range p { p[i] = i } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, log := range logs { t, x, y := log[0], log[1], log[2] if find(x) == find(y) { continue } p[find(x)] = find(y) n if n == 1 { return t } } return 1 }

function earliestAcq(logs: number[][], n: number): number { const p: number[] = Array(n) .fill(0) .map((_, i) => i); const find = (x: number): number => { if (p[x] !== x) { p[x] = find(p[x]); } return p[x]; }; logs.sort((a, b) => a[0]  b[0]); for (const [t, x, y] of logs) { const rx = find(x); const ry = find(y); if (rx !== ry) { p[rx] = ry; if (n === 1) { return t; } } } return 1; }

struct UnionFind { p: Vec<usize>, size: Vec<usize>, } impl UnionFind { fn new(n: usize) > Self { let p: Vec<usize> = (0..n).collect(); let size = vec![1; n]; UnionFind { p, size } } fn find(&mut self, x: usize) > usize { if self.p[x] != x { self.p[x] = self.find(self.p[x]); } self.p[x] } fn union(&mut self, a: usize, b: usize) > bool { let pa = self.find(a); let pb = self.find(b); if pa == pb { false } else if self.size[pa] > self.size[pb] { self.p[pb] = pa; self.size[pa] += self.size[pb]; true } else { self.p[pa] = pb; self.size[pb] += self.size[pa]; true } } } impl Solution { pub fn earliest_acq(logs: Vec<Vec<i32>>, n: i32) > i32 { let mut logs = logs; logs.sort_by(a, b a[0].cmp(&b[0])); let mut uf = UnionFind::new(n as usize); let mut n = n; for log in logs { let t = log[0]; let x = log[1] as usize; let y = log[2] as usize; if uf.union(x, y) { n = 1; if n == 1 { return t; } } } 1 } }