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.
We sort all the logs in ascending order by timestamp, then traverse the sorted logs. Using a union-find set, we check whether the two people in the current log are already friends. If they are not friends, we merge them into one friend circle, until everyone is in one friend circle, then return the timestamp of the current log.
If we have traversed all the logs and not everyone is in one friend circle, then return -1.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of logs.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting + Union-Find | — |
| Default Approach | — |
| 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 |
THE EARLIEST MOMENT WHEN EVERYONE BECOMES FRIENDS | LEETCODE 1101 | PYTHON GRAPH SOLUTION • Cracking FAANG • 5,068 views views
Watch 9 more video solutions →Practice The Earliest Moment When Everyone Become Friends with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor