Moment Everyone Is Linked
MediumGraphs
Problem
A messaging network has n users numbered 0 to n - 1. Each entry [time, a, b] of events records that users a and b connected at that moment; connections are permanent and mutual. The events are not sorted.
Return the earliest time at which every user can reach every other user through connections, or -1 if that never happens.
Example 1
- Input:
- n = 4, events = [[5, 0, 1], [2, 2, 3], [9, 1, 2], [7, 0, 1]]
- Output:
- 9
In time order: 2 joins {2, 3}; 5 joins {0, 1}; 7 adds nothing; 9 links the two groups.
Example 2
- Input:
- n = 3, events = [[1, 0, 1]]
- Output:
- -1
User 2 never connects.
Example 3
- Input:
- n = 3, events = [[4, 0, 1], [4, 1, 2]]
- Output:
- 4
Constraints
- 2 ≤ n ≤ 10^4
- 0 ≤ events.length ≤ 5·10^4
- 0 ≤ time ≤ 10^9
- 0 ≤ a, b < n, a ≠ b
Hint
Show the first hint
If you replay the events in time order, how does the number of groups change?
Walkthrough
How to approach it
01Clarify before coding
- Are events sorted? No, sort them first.
- Can two events share a time? Yes; the answer is still that time.
- What if nobody ever connects everyone? Return -1.
02Brute force
For each candidate time, take all events up to that time and run BFS to see if everyone is connected.
Cost: O(E · (n + E)) checks: about 3·10^9 at the limits. Binary search on time improves it to O((n + E) log E) but is still clumsier.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.