The Earliest Moment When Everyone Became Friends

Given friendship logs with timestamps, return the earliest time when all n people are connected in a single social network. DSU union by rank makes it efficient to merge friendship components while timestamps are processed in sorted order.

Input Format

logs = friendship events with timestamps, n = number of people

Output Format

earliest timestamp when everyone is connected

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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:

20190301

Explanation:

All 6 people become connected for the first time at timestamp 20190301.

Example 2:

Input:

n = 4
logs = [[1,0,1],[2,2,3],[3,1,2]]

Output:

3

Explanation:

The network becomes fully connected when the third log is processed.

Example 3:

Input:

n = 3
logs = [[5,0,1],[10,1,2]]

Output:

10

Explanation:

All three people are connected after the second log.

Loading...
The Earliest Moment When Everyone Became Friends