Problem Brief

Earliest Time All Users Are Connected

FULLTIMEPHONE SCREEN

See Uber online assessment and hiring insights

You are given a list of users and a list of ride-share log entries. Each log entry records a timestamp and two users who shared a ride. Once two users share a ride, they are considered connected. Connectivity is transitive: if A is connected to B and B is connected to C, then A is connected to C.

Each log entry is formatted as "timestamp userA userB", where timestamp is an integer. Process the logs in increasing timestamp order and return the earliest timestamp when all users are connected. If the users never all become connected, return -1.

Function Description

Complete the function earliestFullConnection in the editor.

earliestFullConnection has the following parameters:

String users[]: all users in the system
String logs[]: ride-share connection logs

Returns

int: the earliest timestamp when all users are connected, or -1 if this never happens

1Example 1

Input

users = ["A", "B", "C"], logs = ["1 A B", "3 B C"]

Output

Explanation

At timestamp 1, A and B are connected. At timestamp 3, C joins that component through B, so all users are connected.

2Example 2

Input

users = ["A", "B", "C", "D"], logs = ["5 A B", "1 C D", "10 B C"]

Output

Explanation

The logs are processed by timestamp: C-D at 1, A-B at 5, then B-C at 10 connects the two components.

3Example 3

Input

users = ["A", "B", "C"], logs = ["2 A B"]

Output

-1

Explanation

User C never connects to the A-B component.

Constraints

Limits and guarantees your solution can rely on.

Each log entry has the format "timestamp userA userB".
Logs may be provided out of timestamp order.
User names in logs are included in users.