Medium · Graphs

The Earliest Moment When Everyone Become Friends

Given n people labeled 0 to n − 1 and logs where logs[i] = [timestamp, x, y] means x and y became friends at that time (friendship is mutual, and a friend of a friend counts as acquainted), return the earliest timestamp at which every person is acquainted with every other person, or −1 if that never happens.

Examples

Example 1

{
  "n": 6,
  "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]
  ]
}

Output: earliest = 20190301

Example 2

{
  "n": 5,
  "logs": [
    [10, 0, 1],
    [20, 1, 2],
    [30, 0, 2],
    [40, 2, 3]
  ]
}

Output: earliest = -1

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.