The Earliest Moment When Everyone Become Friends
The Earliest Moment When Everyone Become Friends is a medium graphs problem solved with the connected components pattern.
The best approach, optimal (sort + union-find), runs in O(m log m + m · α(n)) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs after every log) up.
Problem
A group of n people, labelled 0 to n - 1, slowly get to know each other. You are given logs, where logs[i] = [timestamp, x, y] records that x and y became friends at time timestamp. Friendship is mutual and also spreads: if a knows b and b knows c, then a counts as acquainted with c.
Return the earliest timestamp at which every person is acquainted with every other person, or -1 if that never happens.
Examples
Example 1
- Input
logs = [[7,0,1],[3,2,3],[12,1,2],[5,0,1]], n = 4- Output
12- Why
- In time order: 2-3 at 3, 0-1 at 5, 0-1 again at 7 (no change), and 1-2 at 12 finally joins the two pairs.
Example 2
- Input
logs = [[4,0,1],[9,2,3],[6,1,0]], n = 4- Output
-1- Why
- The groups {0, 1} and {2, 3} never get linked.
Example 3
- Input
logs = [[20,2,0],[15,1,2]], n = 3- Output
20- Why
- At time 15 only 1 and 2 know each other; at 20 person 0 joins through 2.
Constraints
2 <= n <= 1001 <= logs.length <= 10^4logs[i] = [timestamp, x, y]with0 <= timestamp <= 10^9and0 <= x, y < n,x != y.- All timestamps are distinct; the same pair may appear more than once.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS after every log) | O(m log m + m · (n + m)) | O(n + m) |
| Optimal (sort + union-find) | O(m log m + m · α(n)) | O(n + m) |
1Brute force (BFS after every log)
O(m log m + m · (n + m))Sorting, then one BFS over at most n people and m edges after each of the m logs.O(n + m)The adjacency list and the BFS state.Sort the logs by time. Add each friendship to an adjacency list and run a BFS from person 0; as soon as the BFS reaches all n people, the current timestamp is the answer.
- Sort
logsby timestamp. - For each log: add the edge in both directions, then BFS from 0 and count the people reached.
- If the count is
n, return the timestamp. If the loop finishes, return -1.
class Solution {
public int earliestAcq(int[][] logs, int n) {
int[][] sorted = logs.clone();
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] log : sorted) {
adj.get(log[1]).add(log[2]);
adj.get(log[2]).add(log[1]);
boolean[] seen = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.add(0);
seen[0] = true;
int reached = 1;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
reached++;
q.add(v);
}
}
}
if (reached == n) return log[0];
}
return -1;
}
}class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
adj = [[] for _ in range(n)]
for t, x, y in sorted(logs):
adj[x].append(y)
adj[y].append(x)
seen = [False] * n
seen[0] = True
q = deque([0])
reached = 1
while q:
u = q.popleft()
for v in adj[u]:
if not seen[v]:
seen[v] = True
reached += 1
q.append(v)
if reached == n:
return t
return -1class Solution {
public:
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<vector<int>> adj(n);
for (auto& log : sorted) {
adj[log[1]].push_back(log[2]);
adj[log[2]].push_back(log[1]);
vector<bool> seen(n, false);
queue<int> q;
q.push(0);
seen[0] = true;
int reached = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!seen[v]) {
seen[v] = true;
reached++;
q.push(v);
}
}
}
if (reached == n) return log[0];
}
return -1;
}
};function earliestAcq(logs, n) {
const sorted = logs.slice().sort((a, b) => a[0] - b[0]);
const adj = Array.from({ length: n }, () => []);
for (const [t, x, y] of sorted) {
adj[x].push(y);
adj[y].push(x);
const seen = new Array(n).fill(false);
seen[0] = true;
const q = [0];
let reached = 1;
for (let h = 0; h < q.length; h++) {
for (const v of adj[q[h]]) {
if (!seen[v]) {
seen[v] = true;
reached++;
q.push(v);
}
}
}
if (reached === n) return t;
}
return -1;
}2Optimal (sort + union-find)
O(m log m + m · α(n))Sorting dominates; each union-find operation is nearly constant.O(n + m)The sorted copy of the logs and the parent array.Sort the logs by time and feed them into a disjoint set union. Each log that joins two different groups lowers the group count by one; the first time the count hits 1, everyone is connected.
- Sort
logsby timestamp;groups = n,parent[i] = i. - For each log, find the roots of x and y (with path compression). If they differ, union them and decrement
groups. - When
groups == 1, return the log's timestamp. Otherwise return -1 after the loop.
class Solution {
private int[] parent;
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int earliestAcq(int[][] logs, int n) {
int[][] sorted = logs.clone();
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (int[] log : sorted) {
int a = find(log[1]), b = find(log[2]);
if (a == b) continue;
parent[a] = b;
if (--groups == 1) return log[0];
}
return -1;
}
}class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
groups = n
for t, x, y in sorted(logs):
a, b = find(x), find(y)
if a == b:
continue
parent[a] = b
groups -= 1
if groups == 1:
return t
return -1class Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
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]; });
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (auto& log : sorted) {
int a = find(log[1]), b = find(log[2]);
if (a == b) continue;
parent[a] = b;
if (--groups == 1) return log[0];
}
return -1;
}
};function earliestAcq(logs, n) {
const sorted = logs.slice().sort((a, b) => a[0] - b[0]);
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let groups = n;
for (const [t, x, y] of sorted) {
const a = find(x), b = find(y);
if (a === b) continue;
parent[a] = b;
if (--groups === 1) return t;
}
return -1;
}Edge cases to test
- Logs are not given in time order
- Fewer than
n - 1logs: the answer must be -1 - Repeated friendships between the same pair (no new link)
- The very last log is the one that completes the group
Hints
Hint 1
Process the logs in increasing order of time; the answer is the time of the first log after which everyone is in one group.
Hint 2
Friendship is transitive here, so this is connectivity. Checking connectivity with a BFS after every log works but repeats a lot of work.
Hint 3
Use a disjoint set union: start with n groups and decrement the count whenever a log merges two different groups. The moment the count reaches 1, return that log's time.
FAQ
What is the best time complexity for The Earliest Moment When Everyone Become Friends?
Optimal (sort + union-find) runs in O(m log m + m · α(n)) time and O(n + m) extra space. Sorting dominates; each union-find operation is nearly constant.
Which pattern does The Earliest Moment When Everyone Become Friends use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.
Is there a brute force solution for The Earliest Moment When Everyone Become Friends?
Yes. Brute force (BFS after every log) takes O(m log m + m · (n + m)) time and O(n + m) space. Sort the logs by time.
Which edge cases should I test for The Earliest Moment When Everyone Become Friends?
Logs are not given in time order; Fewer than n - 1 logs: the answer must be -1; Repeated friendships between the same pair (no new link); The very last log is the one that completes the group.