How should I practice Earliest Time of Full Connection?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Earliest Time of Full Connection associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Earliest Time of Full Connection

Google● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

There are n nodes numbered from 0 to n - 1. Each row [time, u, v] in events records that an undirected connection between nodes u and v becomes available at time.

Connections never disappear. Determine the earliest timestamp at which every node belongs to one connected component. Events may be given in any order, and multiple events may share a timestamp.

Return that earliest timestamp, or -1 if the graph never becomes fully connected.

Function

earliestFullConnection(n: int, events: int[][]) → int

Examples

Example 1

n = 4events = [[5,0,1],[2,2,3],[8,1,2]]return = 8

At time 5, the components are {0,1} and {2,3}. The event at time 8 joins them, so 8 is the first fully connected time.

Example 2

n = 3events = [[4,0,1],[2,1,2],[3,0,2]]return = 3

After sorting by time, 1 and 2 connect at time 2. Node 0 joins that component at time 3.

Example 3

n = 4events = [[1,0,1],[2,2,3]]return = -1

The two connected pairs are never joined, so the graph does not become fully connected.

Constraints

2 <= n <= 100000
0 <= events.length <= 200000
Every event has the form [time, u, v].
0 <= time <= 1000000000
0 <= u, v < n and u != v.
Duplicate connections and equal timestamps are allowed.