Leetcode #1101: The Earliest Moment When Everyone Become Friends
In this guide, we solve Leetcode #1101 The Earliest Moment When Everyone Become Friends in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Union Find, Array, Sorting
Intuition
We need to merge components and check connectivity efficiently.
Union-Find supports near-constant-time merges and finds.
Approach
Initialize each node as its own parent and union pairs as you scan.
Use path compression to keep operations fast.
Steps:
- Initialize parent arrays.
- Union related nodes.
- Use find to check connectivity.
Example
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.
Python Solution
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
for t, x, y in sorted(logs):
if find(x) == find(y):
continue
p[find(x)] = find(y)
n -= 1
if n == 1:
return t
return -1
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.