> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-24-2022-1101.-the-earliest-moment-when-everyone-become-friends.md).

# 06/24/2022 1101. The Earliest Moment When Everyone Become Friends

1101\. The Earliest Moment When Everyone Become Friends

Method: first we need to sort the logs in chronological order. Then we set the groupCount = n first. Then we itertate the logs, for each log, we union the log\[1] and log\[2] and conduct groupCount -= union( og\[1], log\[2]). Then we check if the groupCount == 1, if yes, we return current log\[0]. After the for loop, it means we still have more than 1 group left, then we return -1.

Time O(ElogeE + V + E\* alphaV)

Space(V + logE)

```
// Some code
class Solution {
    public int earliestAcq(int[][] logs, int n) {

        
        // First, we need to sort the events in chronological order.
        //Time O(ElogE) S: O(logE)
        Arrays.sort(logs, (int[] a, int[] b) -> (a[0] - b[0]));

        // Initially, we treat each individual as a separate group.
        int groupCount = n;
        //Time O(V) O(V)
        UnionFind uf = new UnionFind(n);
        
        //O(E*alpha(V))
        for (int[] log : logs) {
            int timestamp = log[0], friendA = log[1], friendB = log[2];

            // We merge the groups along the way.
            groupCount -= uf.union(friendA, friendB);

            // The moment when all individuals are connected to each other.
            if (groupCount == 1) {
                return timestamp;
            }
        }

        // There are still more than one groups left,
        //  i.e. not everyone is connected.
        return -1;
    }
}

class UnionFind {
    private int[] group;
    private int[] rank;

    public UnionFind(int size) {
        this.group = new int[size];
        this.rank = new int[size];
        for (int person = 0; person < size; ++person) {
            this.group[person] = person;
            this.rank[person] = 1;
        }
    }

    /** Return the id of group that the person belongs to. */
    public int find(int person) {
        if (this.group[person] != person)
            this.group[person] = this.find(this.group[person]);
        return this.group[person];
    }

    /**
     * If it is necessary to merge the two groups that x, y belong to.
     * @return true: if the groups are merged.
     */
    public int union(int a, int b) {
        int groupA = this.find(a);
        int groupB = this.find(b);
        //boolean isMerged = false;

        // The two people share the same group.
        if (groupA == groupB)
            return 0;

        // Otherwise, merge the two groups.
       // isMerged = true;
        // Merge the lower-rank group into the higher-rank group.
        else {
            if (this.rank[groupA] > this.rank[groupB]) {
            this.group[groupB] = groupA;
        } else if (this.rank[groupA] < this.rank[groupB]) {
            this.group[groupA] = groupB;
        } else {
            this.group[groupA] = groupB;
            this.rank[groupB] += 1;
        }
            return 1;
        }
        
    }
}
```

```
// Some code
class Solution {
    public int earliestAcq(int[][] logs, int n) {

        // First, we need to sort the events in chronological order.
        Arrays.sort(logs, (int[] a, int[] b) -> (a[0] - b[0]));

        // Initially, we treat each individual as a separate group.
        int groupCount = n;
        UnionFind uf = new UnionFind(n);

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

            // We merge the groups along the way.
            if (uf.union(friendA, friendB)) {
                groupCount -= 1;
            }

            // The moment when all individuals are connected to each other.
            if (groupCount == 1) {
                return timestamp;
            }
        }

        // There are still more than one groups left,
        //  i.e. not everyone is connected.
        return -1;
    }
}

class UnionFind {
    private int[] group;
    private int[] rank;

    public UnionFind(int size) {
        this.group = new int[size];
        this.rank = new int[size];
        for (int person = 0; person < size; ++person) {
            this.group[person] = person;
            this.rank[person] = 0;
        }
    }

    /** Return the id of group that the person belongs to. */
    public int find(int person) {
        if (this.group[person] != person)
            this.group[person] = this.find(this.group[person]);
        return this.group[person];
    }

    /**
     * If it is necessary to merge the two groups that x, y belong to.
     * @return true: if the groups are merged.
     */
    public boolean union(int a, int b) {
        int groupA = this.find(a);
        int groupB = this.find(b);
        boolean isMerged = false;

        // The two people share the same group.
        if (groupA == groupB)
            return isMerged;

        // Otherwise, merge the two groups.
        isMerged = true;
        // Merge the lower-rank group into the higher-rank group.
        if (this.rank[groupA] > this.rank[groupB]) {
            this.group[groupB] = groupA;
        } else if (this.rank[groupA] < this.rank[groupB]) {
            this.group[groupA] = groupB;
        } else {
            this.group[groupA] = groupB;
            this.rank[groupB] += 1;
        }

        return isMerged;
    }
}
```