The Earliest Moment When Everyone Become Friends solution and explanation
Google
8 more videos on this problem
THE EARLIEST MOMENT WHEN EVERYONE BECOMES FRIENDS | LEETCODE 1101 | PYTHON GRAPH SOLUTIONCracking FAANG · 12:02 · 5K views
Union Find | Leetcode 1101. The Earliest Moment When Everyone Become Friends Code with Akhil · 20:00 · 1K views
米开：LeetCode 1101. The Earliest Moment When Everyone Become FriendsM.C米开朗基罗 · 10:10 · 865 views
The Earliest Moment When Everyone Become Friends - Python Union Find SolutionEmily Bao · 11:40 · 839 views
Leetcode 1101. The Earliest Moment When Everyone Become Friends - Disjoint Set / Union-FindCode-Yao · 12:40 · 549 views
[Leetcode] 1101. The Earliest Moment When Everyone Become FriendsSimple Code · 8:04 · 502 views
1101. The Earliest Moment When Everyone Become Friends - Week 1/5 Leetcode July ChallengeProgramming Live with Larry · 8:26 · 427 views
Leetcode 1101DailyLeetcode · 10:55 · 140 views
Solve The Earliest Moment When Everyone Become Friends by general Union-Find Disjoint-SetChier Hu · 8:05 · 98 views
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.
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 != yi- All the values
timestampiare unique. - All the pairs
(xi, yi)occur at most one time in the input.
Approach overview
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 1: Sorting + Union-Find
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.
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 -1class Solution {
private int[] p;
public int earliestAcq(int[][] logs, int n) {
Arrays.sort(logs, (a, b) -> a[0] - b[0]);
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int[] log : logs) {
int t = log[0], x = log[1], y = log[2];
if (find(x) == find(y)) {
continue;
}
p[find(x)] = find(y);
if (--n == 1) {
return t;
}
}
return -1;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int n) {
sort(logs.begin(), logs.end());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) {
return p[x] == x ? x : p[x] = find(p[x]);
};
for (auto& log : logs) {
int x = find(log[1]);
int y = find(log[2]);
if (x != y) {
p[x] = y;
--n;
}
if (n == 1) {
return log[0];
}
}
return -1;
}
};function earliestAcq(logs: number[][], n: number): number {
const p: number[] = Array(n)
.fill(0)
.map((_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
logs.sort((a, b) => a[0] - b[0]);
for (const [t, x, y] of logs) {
const rx = find(x);
const ry = find(y);
if (rx !== ry) {
p[rx] = ry;
if (--n === 1) {
return t;
}
}
}
return -1;
}func earliestAcq(logs [][]int, n int) int {
sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, log := range logs {
t, x, y := log[0], log[1], log[2]
if find(x) == find(y) {
continue
}
p[find(x)] = find(y)
n--
if n == 1 {
return t
}
}
return -1
}struct UnionFind {
p: Vec<usize>,
size: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> Self {
let p: Vec<usize> = (0..n).collect();
let size = vec![1; n];
UnionFind { p, size }
}
fn find(&mut self, x: usize) -> usize {
if self.p[x] != x {
self.p[x] = self.find(self.p[x]);
}
self.p[x]
}
fn union(&mut self, a: usize, b: usize) -> bool {
let pa = self.find(a);
let pb = self.find(b);
if pa == pb {
false
} else if self.size[pa] > self.size[pb] {
self.p[pb] = pa;
self.size[pa] += self.size[pb];
true
} else {
self.p[pa] = pb;
self.size[pb] += self.size[pa];
true
}
}
}
impl Solution {
pub fn earliest_acq(logs: Vec<Vec<i32>>, n: i32) -> i32 {
let mut logs = logs;
logs.sort_by(|a, b| a[0].cmp(&b[0]));
let mut uf = UnionFind::new(n as usize);
let mut n = n;
for log in logs {
let t = log[0];
let x = log[1] as usize;
let y = log[2] as usize;
if uf.union(x, y) {
n -= 1;
if n == 1 {
return t;
}
}
}
-1
}
}Approach 2: Default Approach
class UnionFind:
__slots__ = ('p', 'size')
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x: int) -> int:
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a: int, b: int) -> bool:
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
uf = UnionFind(n)
for t, x, y in sorted(logs):
if uf.union(x, y):
n -= 1
if n == 1:
return t
return -1class UnionFind {
private int[] p;
private int[] size;
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
}
class Solution {
public int earliestAcq(int[][] logs, int n) {
Arrays.sort(logs, (a, b) -> a[0] - b[0]);
UnionFind uf = new UnionFind(n);
for (int[] log : logs) {
int t = log[0], x = log[1], y = log[2];
if (uf.union(x, y) && --n == 1) {
return t;
}
}
return -1;
}
}class UnionFind {
public:
UnionFind(int n) {
p = vector<int>(n);
size = vector<int>(n, 1);
iota(p.begin(), p.end(), 0);
}
bool unite(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private:
vector<int> p, size;
};
class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int n) {
sort(logs.begin(), logs.end());
UnionFind uf(n);
for (auto& log : logs) {
int t = log[0], x = log[1], y = log[2];
if (uf.unite(x, y) && --n == 1) {
return t;
}
}
return -1;
}
};class UnionFind {
private p: number[];
private size: number[];
constructor(n: number) {
this.p = Array(n)
.fill(0)
.map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const pa = this.find(a);
const pb = this.find(b);
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function earliestAcq(logs: number[][], n: number): number {
logs.sort((a, b) => a[0] - b[0]);
const uf = new UnionFind(n);
for (const [t, x, y] of logs) {
if (uf.union(x, y) && --n === 1) {
return t;
}
}
return -1;
}type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func earliestAcq(logs [][]int, n int) int {
sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
uf := newUnionFind(n)
for _, log := range logs {
t, x, y := log[0], log[1], log[2]
if uf.union(x, y) {
n--
if n == 1 {
return t
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting + Union-Find | – |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is The Earliest Moment When Everyone Become Friends easy or hard?
The problem is typically classified as Medium difficulty. The challenge comes from recognizing it as a dynamic connectivity problem and applying Union-Find correctly rather than using repeated graph traversals.
The Earliest Moment When Everyone Become Friends Python/Java solution
Most implementations follow the same pattern: sort logs by timestamp, initialize a Union-Find structure for n people, and process each log with a union operation. When the number of components reaches one, return that timestamp. The approach works the same in Python, Java, C++, Go, and other languages.
How to solve The Earliest Moment When Everyone Become Friends in O(n)?
A true O(n) solution is not possible because the logs must be processed in chronological order, which requires sorting when the input is unsorted. The best achievable complexity is O(m log m) using sorting plus Union-Find. After sorting, each union operation runs in near constant time.
What is the best approach for The Earliest Moment When Everyone Become Friends?
The optimal approach is Sorting + Union-Find. First sort all friendship logs by timestamp, then union the two people in each log using a Disjoint Set Union structure. Track the number of connected components and return the timestamp when it becomes one. The time complexity is O(m log m) due to sorting.
Is The Earliest Moment When Everyone Become Friends asked at Google/Amazon/Meta?
This problem tests dynamic connectivity using Union-Find, a common interview topic at companies like Google, Amazon, and Meta. Variants involving connectivity over time or merging groups appear frequently in system and algorithm interviews.
What data structure is used in The Earliest Moment When Everyone Become Friends?
The key data structure is Union-Find (Disjoint Set Union). It efficiently tracks connected components and supports union and find operations with path compression and union by rank, allowing near constant-time connectivity updates.
What is the time complexity of The Earliest Moment When Everyone Become Friends?
The optimal solution runs in O(m log m) time where m is the number of logs. Sorting the logs dominates the runtime, while each Union-Find operation is nearly constant time with path compression and union by rank. Space complexity is O(n) for storing parent and rank arrays.