Find Earliest Full Connectivity Timestamp

You are given:

• A list of all user IDs in a ride-sharing system.
• A chronological text log of ride-sharing events. Each relevant event contains a timestamp and two users, indicating that the two users shared a ride at that time.

Two users are considered connected if they have directly shared a ride, or if they are connected through a chain of shared rides. For example, if user A shared with user B, and user B shared with user C, then A, B, and C are all connected.

Return the earliest timestamp at which all users in the given user list become part of one connected component.

If the users never all become connected, return an appropriate sentinel value such as -1 or null.

Example:

users = ["A", "B", "C", "D"]
logs = [
 "100 A B shared_ride",
 "120 C D shared_ride",
 "150 B C shared_ride"
]

Output:

150

Explanation: At timestamp 100, A and B are connected. At timestamp 120, C and D are connected. At timestamp 150, the two groups are merged, so all users are connected for the first time.

Follow-up questions:

1. What if the log contains multiple event types, and only some of them should create connections?
2. What if the log is not sorted by timestamp?
3. What is the time complexity of your approach?
4. How would your approach change if the log is very large and must be processed as a stream?