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

Learn to solve Leetcode 1101. The Earliest Moment When Everyone Become Friends with multiple approaches.

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

Sort Logs by Timestamp:
Since we want the earliest time when everyone is connected, process logs in chronological order.
Initialize Union-Find for n nodes.
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.
Return -1 if all logs are processed but not everyone is connected.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Time and Space Complexity

Time Complexity:
- Sorting logs: O(n log n)
- Union-Find operations: nearly O(1) per operation using path compression
- Total: O(n log n)
Space Complexity:
- O(n) for Union-Find arrays

Edge Cases

Logs are empty → return -1
All logs connect the same two people repeatedly → count never becomes 1
Already all connected at the first log → return that timestamp

Relevant Problems

Here are some problems that use similar techniques or concepts (like union-find and graph connectivity) and are relevant to the "Earliest Moment When Everyone Become Friends" problem:

Redundant Connection:
Find an edge that, if removed, leaves a tree. This problem uses Union-Find to detect cycles in a graph.
Accounts Merge:
Given a list of accounts with emails, merge accounts that belong to the same person. This problem also relies on union-find to group related items.
Number of Islands:
Count the number of connected groups (islands) in a 2D grid. This problem involves connectivity and can be solved using DFS/BFS or Union-Find.
Similar String Groups:
Group strings that are similar (i.e., can be transformed into one another by a series of operations). This problem uses union-find to cluster connected components based on similarity.
Satisfiability of Equality Equations:
Determine if a set of equations and inequalities between variables is possible. This problem is solved using union-find to connect variables that must be equal.

Each of these problems helps strengthen your understanding of connectivity, grouping, and the efficient operations provided by union-find.

leetcode

What our users say

Eric

I've completed my first pass of "grokking the System Design Interview" and I can say this was an excellent use of money and time. I've grown as a developer and now know the secrets of how to build these really giant internet systems.

Tonya Sims

DesignGurus.io "Grokking the Coding Interview". One of the best resources I’ve found for learning the major patterns behind solving coding problems.

Arijeet

Just completed the “Grokking the system design interview”. It's amazing and super informative. Have come across very few courses that are as good as this!