The Earliest Moment When Everyone Become Friends

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)