Problem

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3

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 <= timestampi <= 10^9
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • All the values timestampi are unique.
  • All the pairs (xi, yi) occur at most one time in the input.

Solution

Method 1 - Union Find (Disjoint Set Union)

Sort the logs by timestamp, then use union-find to merge friend groups. The earliest time when all are connected is when the number of groups becomes 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <vector>
#include <algorithm>
using namespace std;
struct DSU {
    vector<int> p, sz;
    int cnt;
    DSU(int n): p(n), sz(n,1), cnt(n) { for (int i=0;i<n;++i) p[i]=i; }
    int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int x, int y) {
        int rx=find(x), ry=find(y);
        if (rx==ry) return false;
        if (sz[rx]<sz[ry]) swap(rx,ry);
        p[ry]=rx; sz[rx]+=sz[ry]; --cnt;
        return true;
    }
};
int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    DSU dsu(n);
    for (auto& log : logs) {
        dsu.unite(log[1], log[2]);
        if (dsu.cnt==1) return log[0];
    }
    return -1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, Comparator.comparingInt(a -> a[0]));
        int[] p = new int[n], sz = new int[n];
        for (int i = 0; i < n; ++i) { p[i] = i; sz[i] = 1; }
        int cnt = n;
        for (int[] log : logs) {
            int x = find(p, log[1]), y = find(p, log[2]);
            if (x != y) {
                if (sz[x] < sz[y]) { int t = x; x = y; y = t; }
                p[y] = x; sz[x] += sz[y];
                if (--cnt == 1) return log[0];
            }
        }
        return -1;
    }
    private int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from typing import List
def earliestAcq(logs: List[List[int]], n: int) -> int:
    logs.sort()
    parent = list(range(n))
    size = [1]*n
    groups = n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for t, x, y in logs:
        rx, ry = find(x), find(y)
        if rx != ry:
            if size[rx] < size[ry]: rx, ry = ry, rx
            parent[ry] = rx
            size[rx] += size[ry]
            groups -= 1
            if groups == 1:
                return t
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub fn earliest_acq(mut logs: Vec<Vec<i32>>, n: i32) -> i32 {
    logs.sort();
    let mut parent: Vec<i32> = (0..n).collect();
    let mut size = vec![1; n as usize];
    let mut groups = n;
    fn find(parent: &mut Vec<i32>, x: i32) -> i32 {
        if parent[x as usize] != x {
            parent[x as usize] = find(parent, parent[x as usize]);
        }
        parent[x as usize]
    }
    for log in logs {
        let (t, x, y) = (log[0], log[1], log[2]);
        let (mut rx, mut ry) = (find(&mut parent, x), find(&mut parent, y));
        if rx != ry {
            if size[rx as usize] < size[ry as usize] { std::mem::swap(&mut rx, &mut ry); }
            parent[ry as usize] = rx;
            size[rx as usize] += size[ry as usize];
            groups -= 1;
            if groups == 1 { return t; }
        }
    }
    -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function earliestAcq(logs: number[][], n: number): number {
    logs.sort((a, b) => a[0] - b[0]);
    const parent = Array.from({length: n}, (_, i) => i);
    const size = Array(n).fill(1);
    let groups = n;
    function find(x: number): number {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    for (const [t, x, y] of logs) {
        let rx = find(x), ry = find(y);
        if (rx !== ry) {
            if (size[rx] < size[ry]) [rx, ry] = [ry, rx];
            parent[ry] = rx;
            size[rx] += size[ry];
            groups--;
            if (groups === 1) return t;
        }
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(M log M + M α(N)) where M = logs.length, N = n, and α is the inverse Ackermann function.
  • 🧺 Space complexity: O(N)