LeetCode Solutions Blog

The Earliest Moment When Everyone Become Friends

Number: 1085

Difficulty: Medium

Paid? Yes

Problem Description

We are given n people (labeled from 0 to n - 1) and a list of friendship events, where each event is represented by a log entry [timestamp, x, y]. At the given timestamp, person x and person y become friends. Friendship is both symmetric and transitive (i.e., a friend of a friend is also considered a friend). The goal is to determine the earliest timestamp at which all n people are connected (acquainted) with each other. If it is never possible for everyone to be connected, return -1.

Key Insights

Sort the logs by their timestamps so that events are processed in chronological order.
Use the Union-Find (disjoint-set) data structure to efficiently merge friendship groups.
Maintain a count of connected components; when this count reaches 1, everyone is connected.
If after processing all events the count is greater than 1, return -1.

Space and Time Complexity

Time Complexity: O(M log M + M * α(n)) where M is the number of log entries and α is the Inverse Ackermann function (nearly constant in practice). Space Complexity: O(n) for storing parent and rank arrays in the Union-Find structure.

Solution

The solution starts by sorting the log entries based on the timestamp to simulate the passage of time. We then initialize a Union-Find data structure with n disjoint sets (one for each person). For each log entry (friendship event), we perform a union operation to merge the sets of the two people involved. After each union, we check if we have only one connected component (i.e., all people are connected). If so, the current timestamp is the earliest moment when everyone becomes friends. If no such moment is reached by the end of the logs, we return -1.

Code Solutions

# Define the Union-Find class with path compression and union by rank.
class UnionFind:
    def __init__(self, n):
        # Initialize parent pointers: each node is its own parent.
        self.parent = list(range(n))
        # Initialize rank for union by rank optimization.
        self.rank = [0] * n
        # Initially, there are n separate sets.
        self.count = n

    def find(self, x):
        # Recursively find the root, applying path compression.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Find the roots of x and y.
        rootX = self.find(x)
        rootY = self.find(y)
        # If they are already in the same set, no union is needed.
        if rootX == rootY:
            return False
        # Merge the smaller tree under the larger one using rank.
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        # Decrement the count of disjoint sets.
        self.count -= 1
        return True

def earliestAcq(logs, n):
    # Sort the logs by timestamp.
    logs.sort(key=lambda x: x[0])
    uf = UnionFind(n)
    # Process each log in chronological order.
    for timestamp, x, y in logs:
        uf.union(x, y)
        # Return the timestamp when all persons are connected.
        if uf.count == 1:
            return timestamp
    return -1

# Example usage:
if __name__ == '__main__':
    logs = [
        [20190101, 0, 1], [20190104, 3, 4], [20190107, 2, 3],
        [20190211, 1, 5], [20190224, 2, 4], [20190301, 0, 3],
        [20190312, 1, 2], [20190322, 4, 5]
    ]
    n = 6
    print(earliestAcq(logs, n))