Earliest Moment Everyone Becomes Friends [Union Find]

XXX. Earliest Moment When Everyone Becomes Friends

Graph

Union-Find

Problem Statement:

You are given a list of logs, where each log contains a timestamp, and two people who became friends at that timestamp. The task is to determine the earliest time when everyone in a group of n people is connected, meaning that there is a path of friendships between every pair of people.

Algorithm:

1. Sort the logs by their timestamps.
2. Initialize a union-find structure to keep track of connected components.
3. Iterate over the sorted logs:
   • For each log, find the roots of the two people becoming friends.
   • If they are not already connected, union them and decrease the group count.
   • If the group count reaches 1, return the current timestamp.
4. If the group count never reaches 1, return -1.

Complexity:

Time Complexity: O(E log E + E α(n)), where E is the number of logs and α is the inverse Ackermann function for union-find operations.
Space Complexity: O(n) for the union-find structure.

Java Implementation:

public int earliestAcq(int[][] logs, int n) {
    // Sort logs by timestamp
    Arrays.sort(logs, new Comparator() {
        @Override
        public int compare(int[] log1, int[] log2) {
            return Integer.compare(log1[0], log2[0]);
        }
    });

    // Initialize union-find structure
    int[] parent = new int[n];
    Arrays.fill(parent, -1);

    int groupCount = n;

    for (int[] log : logs) {
        int timestamp = log[0];
        int friendA = log[1];
        int friendB = log[2];

        // Find the root of each friend
        int rootA = find(friendA, parent);
        int rootB = find(friendB, parent);

        // If they are not already connected, union them
        if (rootA != rootB) {
            union(rootA, rootB, parent);
            groupCount--;
        }

        // Check if everyone is connected
        if (groupCount == 1) {
            return timestamp;
        }
    }

    // If we never reach a single group, return -1
    return -1;
}

public int find(int i, int[] parent) {
    if (parent[i] == -1) 
        return i;
    parent[i] = find(parent[i], parent); // Path compression
    return parent[i];
}

public void union(int x, int y, int[] parent) {
    parent[find(y, parent)] = find(x, parent);
}
                

Python Implementation:

def earliest_acq(logs, n):
    # Sort logs by timestamp
    logs.sort(key=lambda log: log[0])

    # Initialize union-find structure
    parent = [-1] * n

    def find(i):
        if parent[i] == -1:
            return i
        parent[i] = find(parent[i])  # Path compression
        return parent[i]

    def union(x, y):
        parent[find(y)] = find(x)

    group_count = n

    for timestamp, friend_a, friend_b in logs:
        root_a = find(friend_a)
        root_b = find(friend_b)

        if root_a != root_b:
            union(root_a, root_b)
            group_count -= 1

        if group_count == 1:
            return timestamp

    return -1
                

C++ Implementation:

#include 
#include 
using namespace std;

int earliestAcq(vector>& logs, int n) {
    // Sort logs by timestamp
    sort(logs.begin(), logs.end(), [](const vector& log1, const vector& log2) {
        return log1[0] < log2[0];
    });

    // Initialize union-find structure
    vector parent(n, -1);

    auto find = [&](int i) {
        if (parent[i] == -1)
            return i;
        return parent[i] = find(parent[i]);  // Path compression
    };

    auto union_sets = [&](int x, int y) {
        parent[find(y)] = find(x);
    };

    int group_count = n;

    for (const auto& log : logs) {
        int timestamp = log[0], friend_a = log[1], friend_b = log[2];

        int root_a = find(friend_a);
        int root_b = find(friend_b);

        if (root_a != root_b) {
            union_sets(root_a, root_b);
            group_count--;
        }

        if (group_count == 1)
            return timestamp;
    }

    return -1;
}