Connected regions and dependencies: A Sample Coding Interview Solution

The coding question

You're given logs of riders who shared a ride, sorted by time. Return the earliest time when every rider is connected to every other, directly or through other riders, or -1 if that never happens.

Ask a few questions first

Ask	What we'll assume
What does a log look like?	A tuple (time, a, b), meaning riders a and b shared a ride at that time.
How do we know who all the riders are?	You're given n, and riders are numbered 0 to n - 1.
Does connected carry through other riders?	Yes. If a rode with b and b rode with c, then a and c are connected.
What if there's only one rider?	They're already connected to everyone, so return 0.

A couple of examples

Input	Output
n = 4, logs [(1, 0, 1), (3, 2, 3), (5, 1, 2)]	5, since the ride at time 5 joins {0, 1} and {2, 3}
n = 4, logs [(2, 0, 1), (4, 2, 3)]	-1, since the two pairs never meet
n = 3, logs [(1, 0, 1), (2, 1, 0), (6, 1, 2)]	6, and the ride at time 2 changes nothing

Start with brute force

After each log, build the graph of rides so far and run a breadth-first search from rider 0. The first time it reaches all n riders, return that log's time.

Cost: a full search after every log is O(m × (n + m)) for m logs. Fine for a few hundred, too slow for 100,000.

A better way

Riders are nodes and rides are edges. It's a graph, even though nobody said graph. We're asking when the whole thing becomes one connected group.

Logs only ever add edges, and they're sorted by time. So keep track of groups as we go with union-find. Start with n groups of one. Each ride either joins two different groups, which drops the count by one, or it's inside a group already and changes nothing. The moment the count hits 1, that's the answer.

Give every rider a parent pointer to themselves, and set groups = n.
find(x) follows parent pointers up to the group's root, shortening the path as it goes.
For each log in order, find the roots of both riders.
If the roots differ, point one at the other and drop groups by one. If groups is now 1, return the time.
If the logs run out with more than one group, return -1.

The code

solution.pypython

def earliest_all_connected(logs, n):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # point halfway up as we go
            x = parent[x]
        return x

    groups = n
    for time, a, b in logs:
        root_a, root_b = find(a), find(b)
        if root_a != root_b:
            parent[root_a] = root_b
            groups -= 1
            if groups == 1:
                return time
    return -1 if groups > 1 else 0

	Cost	Why
Time	About O(n + m)	Each find is close to constant with path shortening, and we do two per log
Space	O(n)	One parent pointer per rider

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

One rider: groups starts at 1, the loop never returns, and we return 0.
No logs with two or more riders: groups stays above 1, so -1.
The same pair riding twice: the second time, both have the same root and nothing changes.
A rider riding with themselves: same root, nothing changes.
Everyone connects on the very first log, like n = 2: we return that log's time.

Common mistakes

Running a full search after every log, which is the brute force again.
Counting distinct riders seen instead of groups. Everyone can show up in a log while still being in two separate groups.
Lowering the group count even when both riders already share a root.
Forgetting to sort the logs if the interviewer says they might not be sorted.

Follow-up questions

What if the logs aren't sorted?

Sort them by time first. That's O(m log m), and the rest stays the same.

What if they ask for a task order from dependencies instead?

That's a directed graph, so union-find doesn't fit. Count how many tasks each one waits on, start with the ones waiting on nothing, and if tasks are left over at the end, there's a loop.

What if riders can leave a group?

Union-find can't undo a join. If removals are rare, rebuild. Otherwise, process everything in reverse, so removals become joins.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force and what it costs
10–15	Explain the better idea
15–30	Write the code
30–38	Test it out loud
38–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Uber.