1101. The Earliest Moment When Everyone Become Friends

Intuition

This problem is about determining when a group of people becomes fully connected through friendships. Since friendships can spread indirectly (via mutual acquaintances), we can model the network using Union-Find (Disjoint Set Union). Each person starts in their own group, and as we process friendship logs (sorted by time), we gradually merge these groups. When there's only one group left, everyone is connected.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(L*\log{L} + L*N)$

Code

class UnionFind {
    int[] parent;
    int[] rank;

    // Initialize Union-Find data structure
    UnionFind(int totalPeople) {
        parent = new int[totalPeople];
        rank = new int[totalPeople];

        for (int i = 0; i < totalPeople; ++i) {
            parent[i] = i;  // Each person is initially their own parent
            rank[i] = 0;    // Initial rank is zero
        }
    }

    // Find the representative (root parent) of the given node
    public int findRepresentative(int person) {
        int representative = parent[person];

        // Path compression for efficiency
        while (representative != parent[representative]) {
            representative = parent[representative];
        }

        // Directly link the current node to its root parent
        parent[person] = representative;

        return representative;
    }

    // Union two groups (friend circles)
    public void union(int personA, int personB) {
        int repA = findRepresentative(personA);
        int repB = findRepresentative(personB);

        // If they already belong to the same group, do nothing
        if (repA == repB) return;

        // Union by rank to maintain a shallow tree
        if (rank[repA] > rank[repB]) {
            parent[repB] = repA;
        } else if (rank[repA] < rank[repB]) {
            parent[repA] = repB;
        } else {
            parent[repA] = repB;
            rank[repB]++;
        }
    }

    // Check if all people share the same parent (i.e., are fully connected)
    public boolean areAllConnected() {
        int rootParent = -1;

        for (int i = 0; i < parent.length; ++i) {
            int currentParent = findRepresentative(i);

            if (rootParent != -1 && rootParent != currentParent) {
                return false;
            }

            rootParent = currentParent;
        }

        return true;
    }
}

public int earliestAcq(int[][] logs, int totalPeople) {
    // Sort logs by timestamp to simulate events in order
    Arrays.sort(logs, (log1, log2) -> Integer.compare(log1[0], log2[0]));

    UnionFind unionFind = new UnionFind(totalPeople);

    // Process each friendship log
    for (int i = 0; i < logs.length; ++i) {
        int timestamp = logs[i][0];
        int personX = logs[i][1];
        int personY = logs[i][2];

        // Union the two people
        unionFind.union(personX, personY);

        // Check if everyone is now connected
        if (unionFind.areAllConnected()) {
            return timestamp;
        }
    }

    // Not all people became friends
    return -1;
}