MediumNo. 1101LeetCode Premium
The Earliest Moment When Everyone Become Friends — LeetCode 1101 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Array, Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
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].
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 -1Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1101. The Earliest Moment When Everyone Become Friends is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1697 | Checking Existence of Edge Length Limited Paths | Hard |
| 1998 | GCD Sort of an Array | Hard |
| 2948 | Make Lexicographically Smallest Array by Swapping Elements | Medium |
| 0803 | Bricks Falling When Hit | Hard |
| 1627 | Graph Connectivity With Threshold | Hard |
| 2382 | Maximum Segment Sum After Removals | Hard |
Frequently asked questions
- How hard is LeetCode 1101. The Earliest Moment When Everyone Become Friends?
LeetCode 1101. The Earliest Moment When Everyone Become Friends is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1101. The Earliest Moment When Everyone Become Friends cover?
LeetCode 1101. The Earliest Moment When Everyone Become Friends is tagged Union Find, Array and Sorting on LeetCode.
- Is LeetCode 1101. The Earliest Moment When Everyone Become Friends a premium problem?
Yes. LeetCode 1101. The Earliest Moment When Everyone Become Friends is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.