The Earliest Moment When Everyone Become Friends — Solution
The Earliest Moment When Everyone Become Friends solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
The Earliest Moment When Everyone Become Friends is a medium coding problem on arrays, sorting and union find, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Union Find
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In a group of n people numbered 0 through n - 1, logs[i] = [timestamp, x, y] records that x and y became friends at that time. Friendship is mutual and transitive: friends of friends are acquainted.
Return the earliest timestamp at which everyone is acquainted with everyone else, or -1 if that never happens.
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
Example 2
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Example 3
Input: logs = [[0,0,1]], n = 3
Output: -1
Constraints
1 <= n <= 401 <= logs.length <= 60All timestamps are distinct.
Follow-up: Sorting dominates the running time. Can you keep the union-find part almost linear?
Hints for The Earliest Moment When Everyone Become Friends
Hint 1
Process the friendships in chronological order, so sort the logs by timestamp first.
Hint 2
Union-find tracks how many separate groups remain, starting at
n.Hint 3
The moment the group count drops to 1 is the answer; if it never does, return
-1.
How to solve The Earliest Moment When Everyone Become Friends
Process friendships in time order with union-find; the timestamp that reduces the group count to 1 is the answer.
Approach
- Sort logs by timestamp.
- For each log, union the pair; if it merges two groups and the count reaches 1, return the timestamp.
- Return -1 if never.
Why it works
Acquaintance is transitive closure of friendship, which is exactly the component structure; processing chronologically finds the first moment a single component forms.
Complexity
- Time —
O(m log m + m · α(n)) - Space —
O(n)
Pitfalls
- With
n = 1everyone is already acquainted at time 0.
Reference solution
Python
def earliestAcq(logs, n: int) -> int:
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
groups = n
for timestamp, x, y in sorted(logs):
rx, ry = find(x), find(y)
if rx != ry:
parent[rx] = ry
groups -= 1
if groups == 1:
return timestamp
return 0 if groups == 1 else -1Java
private static int findRoot(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public static int earliestAcq(int[][] logs, int n) {
int[][] sorted = logs.clone();
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (int[] entry : sorted) {
int a = findRoot(parent, entry[1]);
int b = findRoot(parent, entry[2]);
if (a != b) {
parent[a] = b;
groups--;
if (groups == 1) return entry[0];
}
}
return groups == 1 ? 0 : -1;
}C++
static int findRoot(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
int earliestAcq(vector<vector<int>>& logs, int n) {
vector<vector<int>> sorted = logs;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (const auto& entry : sorted) {
int a = findRoot(parent, entry[1]);
int b = findRoot(parent, entry[2]);
if (a != b) {
parent[a] = b;
groups--;
if (groups == 1) return entry[0];
}
}
return groups == 1 ? 0 : -1;
}JavaScript
var earliestAcq = function(logs, n) {
const sorted = logs.slice().sort(function(a, b) { return a[0] - b[0]; });
const parent = [];
for (let i = 0; i < n; i++) parent.push(i);
const find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let groups = n;
for (let i = 0; i < sorted.length; i++) {
const a = find(sorted[i][1]);
const b = find(sorted[i][2]);
if (a !== b) {
parent[a] = b;
groups--;
if (groups === 1) return sorted[i][0];
}
}
return groups === 1 ? 0 : -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms