Watch 10 video solutions for The Earliest Moment When Everyone Become Friends, a medium level problem involving Array, Union Find, Sorting. This walkthrough by Cracking FAANG has 5,068 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.
Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.
Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.
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],[20190322,4,5]], n = 6 Output: 20190301 Explanation: The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5]. The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5]. The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5]. The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4]. The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens. The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.
Example 2:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
Constraints:
2 <= n <= 1001 <= logs.length <= 104logs[i].length == 30 <= timestampi <= 1090 <= xi, yi <= n - 1xi != yitimestampi are unique.(xi, yi) occur at most one time in the input.Problem Overview: You receive friendship logs in the format [timestamp, personA, personB]. Each log means two people became friends at that time. The goal is to return the earliest timestamp when everyone in a group of n people becomes connected through direct or indirect friendships.
Approach 1: Incremental Graph + Connectivity Check (Brute Force) (Time: O(m * n), Space: O(n + m))
Process logs in chronological order and build a graph where nodes represent people and edges represent friendships. After each log, run a traversal such as DFS or BFS to check if all n nodes are connected. This requires iterating through the adjacency list and visiting every node, which costs O(n + m) per check. Repeating this after each friendship event leads to roughly O(m * n) time in dense scenarios. This approach works for small inputs but becomes slow when the number of logs grows.
Approach 2: Sorting + Union-Find (Optimal) (Time: O(m log m), Space: O(n))
Sort the logs by timestamp, then process them in chronological order. Use a Disjoint Set Union (DSU) structure to track connected components. Each friendship event performs a union(a, b), merging two groups if they were previously separate. Maintain a counter of remaining components; once it becomes 1, everyone is connected. Union-Find with path compression and union by rank keeps operations nearly constant time. The dominant cost becomes sorting the logs (O(m log m)), making this approach scalable for large inputs.
The key insight: the earliest moment when everyone becomes friends is exactly when the number of connected components drops to one. Union-Find tracks this efficiently without repeatedly traversing the graph.
Relevant concepts include Union-Find, Sorting, and Array processing for handling the input logs.
Recommended for interviews: Sorting + Union-Find is the expected solution. Interviewers want to see that you recognize this as a dynamic connectivity problem. Showing the brute-force graph traversal demonstrates baseline reasoning, but implementing Union-Find proves you understand scalable connectivity algorithms.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Incremental Graph + DFS/BFS Connectivity Check | O(m * n) | O(n + m) | Useful for understanding the problem or when constraints are small |
| Sorting + Union-Find | O(m log m) | O(n) | Best general solution for large inputs and typical interview expectations |