The Earliest Moment When Everyone Become Friends - Leetcode Solution

Problem:

There are n people in a social group labeled from 0 to n-1. You are given a log file logs where logs[i] = [timestamp_i, from_i, to_i] indicates that from_i and to_i became friends at the time timestamp_i.

Back to present time, all friendships are formed. You need to find the earliest time when everyone in the group became friends. If there is no such a time, return -1.

Example 1:

Input: n = 2, logs = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,3,4],[3,4,5]], Output: 3 Explanation: The earliest time when everyone became friends is 3. At time 3, group 1 [0,1,2,3,4,5] became friends.

Solution:

To solve this problem, we can use Union Find data structure. We need to maintain a parent array where parent[i] will store the parent node of i. Initially, all nodes will be the parent of themselves. We also need to maintain a rank array where rank[i] will store the rank of i.

The rank is used to maintain the height of the tree. We try to merge smaller trees with bigger trees to get a more balanced tree and thus more efficient Union Find operations.

The day when everyone becomes friends is when the number of connected components reduces to one. We can keep track of the number of connected components using a variable count.

Initially, when all n nodes are not connected to any other node, count=n. For each log, we check whether the from and to nodes are already connected or not using find function. If the nodes are not connected, we merge them using union function and reduce count by one.

We keep doing this until count becomes one or we have checked all logs. If count never becomes one, that means all nodes are not connected with each other, so we return -1. Otherwise, we return the timestamp at which all nodes are connected.

Implementation:

Here is the Python code for the implementation:

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0]*n
        self.count = n

    def find(self, i: int) -> int:
        while i != self.parent[i]:
            self.parent[i] = self.parent[self.parent[i]]
            i = self.parent[i]
        return i

    def union(self, i: int, j: int) -> bool:
        parent_i, parent_j = self.find(i), self.find(j)
        if parent_i == parent_j:
            return False
        if self.rank[parent_i] < self.rank[parent_j]:
            parent_i, parent_j = parent_j, parent_i
        self.parent[parent_j] = parent_i
        if self.rank[parent_i] == self.rank[parent_j]:
            self.rank[parent_i] += 1
        self.count -= 1
        return True

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        logs.sort()
        uf = UnionFind(n)
        for log in logs:
            uf.union(log[1], log[2])
            if uf.count == 1:
                return log[0]
        return -1

Time Complexity: The time complexity of this algorithm is O(nlogn) where n is the number of logs. Sorting of logs takes O(nlogn) time. The for loop runs n times and inside the loop, we do find and union operations which take O(alpha(n)) time (almost constant time) where alpha(n) is the inverse Ackermann function which is a very slowly growing function.

Space Complexity: The space complexity of this algorithm is O(n) where n is the number of nodes. We need to maintain a parent and rank array for each node.

1