# 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

```java
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;
}

```