Earliest Time Everyone Is Connected
Asked at Google· Onsite
Reported by the problem's creator, not verified
n people are labeled 0 to n - 1. A log entry [timestamp, a, b] says that at timestamp, people a and b become friends. Entries are not sorted and all timestamps are distinct. Every entry is valid: it joins two people who are not yet friends. Entries take effect in increasing timestamp order.
Two people are acquainted if they are friends or connected through a chain of friends. Implement earliest_connected(n, logs), which returns the smallest timestamp at which everyone is acquainted with everyone else, or -1 if that never happens.
Examples
Example 1
Input: n =
4, logs =[[20,2,3],[5,0,1],[12,1,2],[30,0,3]]Output:
20Explanation: In time order: 0-1 at 5, 1-2 at 12, 2-3 at 20. After time 20 all four people are in one group, so the answer is 20; the later event at 30 does not matter.