1101. The Earliest Moment When Everyone Become Friends - Detailed Explanation

Problem Statement

You are given a list of logs where each entry is of the form [timestamp, personA, personB], indicating that personA and personB became friends at that specific time.

You are also given n, the total number of people labeled from 0 to n - 1. A friendship is transitive, meaning if A is friends with B, and B is friends with C, then A is also friends with C.

Return the earliest time when all people become friends — i.e., there is only one connected group of all n people. If it’s impossible for everyone to become friends, return -1.

Hints

Here are some hints to help you solve the problem:

• Sort by Time:
  Since you're looking for the earliest moment when everyone is connected, try sorting the logs by their timestamp. Processing them in chronological order will allow you to simulate the friendships as they happen.

• Use Union-Find (Disjoint Set):
  Think about how you can model the friendships as a connectivity problem. A Union-Find data structure is ideal for merging groups (friends) and quickly checking if everyone is connected.

• Union and Count Components:
  As you process each log (i.e., each friendship event), perform a union operation for the two people involved. Keep track of the total number of connected components. The goal is to reach a state where there is only one connected component.

• Optimize with Path Compression and Union by Rank:
  To handle many union and find operations efficiently, consider implementing path compression and union by rank in your Union-Find. This will help you perform operations nearly in constant time.

• Check for Early Termination:
  As soon as you notice that all individuals are connected (only one group remains), you can return the current timestamp immediately.

Example 1

Input:

logs = [[20190101, 0, 1], [20190104, 3, 4], [20190107, 2, 3], [20190211, 1, 5],
        [20190224, 2, 4], [20190301, 0, 3], [20190312, 1, 2]]
n = 6

Output:

20190301

Explanation: On 20190301, the last connection (0,3) merges all individuals into one group.

Key Insight

This problem is a classic Dynamic Connectivity problem. We are asked to process a series of union (merge) operations in chronological order and determine the first time when all individuals belong to a single connected component.

We can solve this efficiently using a Disjoint Set Union (DSU) or Union-Find data structure.

Union-Find Data Structure

Union-Find maintains a collection of disjoint sets and supports two operations:

• Find(x): Returns the representative (root) of the set that contains x.
• Union(x, y): Merges the sets containing x and y.

To speed up operations, we apply:

• Path compression: Flatten the tree when performing find, making future operations faster.
• Union by rank / size: Always attach the smaller tree under the larger one.

Algorithm Steps

1. Sort Logs by Timestamp:
   Since we want the earliest time when everyone is connected, process logs in chronological order.

2. Initialize Union-Find for n nodes.

3. Iterate Through Logs:

   • For each log [timestamp, a, b], perform union(a, b).
   • After each union, check how many components remain.
   • If all people are connected (i.e., there's only 1 component), return the current timestamp.

4. Return -1 if all logs are processed but not everyone is connected.

Python Code