Generated by Codex with GPT-5

Quick facts

What the problem is really asking

There are n people labeled from 0 to n - 1. The input is a list of friendship events. Each event has a timestamp and two people, meaning those two people become direct friends at that moment.

Friendship is also transitive. If 0 is friends with 1, and 1 is friends with 2, then all three people are in the same friend group. The task is to return the earliest timestamp when there is only one friend group left, meaning every person is connected to every other person through some chain of friendships.

If the events never connect everyone, return -1.

The problem is not asking for the shortest chain between people or the final friend graph. It is asking when a graph first becomes connected as edges are added over time.

The optimal idea

The timestamps matter, so process the friendship events in chronological order. After each event, the only important question is whether it joined two previously separate friend groups.

That is exactly what a union-find data structure tracks efficiently:

  • find(person) returns the current representative of that person’s friend group.
  • union(a, b) merges two friend groups if they are different.
  • a component count tracks how many separate friend groups still exist.

Start with n components, because every person is alone. Sort the logs by timestamp. For each friendship, union the two people. Whenever a union actually merges two groups, reduce the component count by one. The first timestamp where the component count becomes 1 is the answer.

Sorting costs O(m log m) for m logs. The union-find operations are almost constant time, so the total runtime is O(m log m) and the extra space is O(n).

How to derive it in an interview

A direct simulation could build the graph after every timestamp and run a DFS or BFS to check whether all people are connected. That works conceptually, but it repeats too much work. If there are many logs, rechecking the whole graph after each event can become expensive.

The key observation is that friendships only get added. Once two groups become connected, they never split apart in the original problem. So instead of rebuilding connectivity from scratch, keep the connected groups incrementally.

That turns the problem into a sequence of merge operations:

  1. Before seeing any logs, there are n separate groups.
  2. A friendship between people in different groups reduces the number of groups by one.
  3. A friendship inside the same group changes nothing.
  4. The first time the group count reaches 1, everyone is connected.

Union-find is the standard tool for exactly this kind of “merge groups and ask whether two items are already connected” problem.

Python solution

from typing import Sequence


class DisjointSet:
    """Union-find with path compression and union by size."""

    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.component_size = [1] * size
        self.component_count = size

    def find(self, node: int) -> int:
        """Return the representative for node's current component."""
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, first: int, second: int) -> bool:
        """
        Merge two components.

        Return True only when the merge actually connects two previously
        separate groups.
        """
        first_root = self.find(first)
        second_root = self.find(second)

        if first_root == second_root:
            return False

        if self.component_size[first_root] < self.component_size[second_root]:
            first_root, second_root = second_root, first_root

        self.parent[second_root] = first_root
        self.component_size[first_root] += self.component_size[second_root]
        self.component_count -= 1
        return True


def earliest_time_everyone_connected(
    logs: Sequence[Sequence[int]],
    person_count: int,
) -> int:
    """
    Return the earliest timestamp when all people belong to one friend group.

    Each log entry is [timestamp, person_a, person_b].
    """
    if person_count <= 1:
        return 0

    friend_groups = DisjointSet(person_count)

    for timestamp, first_person, second_person in sorted(
        logs,
        key=lambda entry: entry[0],
    ):
        friend_groups.union(first_person, second_person)

        if friend_groups.component_count == 1:
            return timestamp

    return -1


class Solution:
    def earliestAcq(self, logs: list[list[int]], n: int) -> int:
        """LeetCode entry point."""
        return earliest_time_everyone_connected(logs, n)

Why this works

After processing all logs up to a given timestamp, the union-find structure represents exactly the connected components created by those friendships. This is true at the start because every person is alone. It remains true after each log because unioning the two people adds precisely the new friendship edge and merges their two components if that edge connects separate groups.

The component count is therefore the number of current friend groups. When it becomes 1, all people are in the same connected component, so everyone is acquainted through some chain of friendships.

Processing logs in sorted timestamp order is what makes the first time with one component the earliest possible answer. If a later timestamp connects everyone, the algorithm will find it only after proving that no earlier processed timestamp already did.

Repeated friendships and friendships within an already connected group are harmless. union returns False for those cases and leaves the component count unchanged.

Complexity

Let m be the number of logs and n be the number of people.

Sorting the logs costs O(m log m). Each union-find operation costs amortized O(alpha(n)), where alpha is the inverse Ackermann function and is effectively constant for interview-sized inputs. The total time complexity is therefore O(m log m).

The union-find arrays use O(n) extra space. Sorting may use additional implementation-dependent space, but the main data structure is linear in the number of people.

Interview follow-ups

What if the logs are already sorted by timestamp?

Then the sorting step can be skipped. The solution becomes a single left-to-right scan over the logs, unioning each friendship and returning as soon as the component count reaches one. The correctness argument is the same because the algorithm still processes events in chronological order. The runtime improves from O(m log m) to O(m alpha(n)), which is effectively linear, while the space remains O(n).

What if several friendships have the same timestamp?

The basic solution still works because all events with the same timestamp happen at the same time for the purpose of the answer. If one event at timestamp t makes the component count reach one, returning t is correct even if other events with timestamp t appear later in the sorted order.

If the interviewer wants the complete state at that timestamp, process logs in timestamp groups instead. Union every friendship in the group first, then check whether everyone is connected after the whole group. That produces the same earliest timestamp, but it also gives a cleaner snapshot of the final groups at that time. The runtime stays dominated by sorting.

What if the interviewer asks for the friend groups at the earliest time?

Use the same chronological union-find scan. When the component count becomes one, the answer is already a single group, so the group list is trivial. A more useful variant is asking for the groups just before everyone becomes connected. In that case, keep a snapshot before processing each timestamp group or rebuild the groups from the union-find parents before applying the final timestamp’s merges.

The tradeoff is that materializing groups costs extra work. Building a dictionary from root representative to people takes O(n alpha(n)) at the moment you need the snapshot. That is fine for one snapshot, but expensive if repeated after every log.

What if friendships can expire or be deleted?

Plain union-find is no longer enough because it handles merges efficiently but does not split components. Once two groups are unioned, the data structure has no cheap way to undo that connection while preserving all other friendships.

For a small input, the practical answer is to rebuild connectivity after each deletion with DFS, BFS, or a fresh union-find pass. For a larger system, this becomes a dynamic connectivity problem. More advanced structures can support edge additions and removals, but they are significantly more complex. The important interview tradeoff is that the original monotonic “friendships only get added” property is what makes union-find the simple optimal fit.

How would you answer many queries like “are these two people connected at time T?”

One approach is to sort the logs once and sort the queries by time. Then sweep forward through the logs, unioning every friendship whose timestamp is at most the current query time, and answer the query with find(a) == find(b). This works when queries are processed offline in nondecreasing time because connectivity only grows as time increases.

The cost is O((m + q) log(m + q)) for sorting plus near-constant union-find work, where q is the number of queries. The tradeoff is that this offline method does not support arbitrary time travel after unions have already been applied. If queries must arrive online in any order, the solution needs persistent or rollback union-find, or it must rebuild from the beginning for each earlier time.

Practical takeaway

This problem is a clean example of recognizing incremental connectivity. Sorting puts events in the only order that can define “earliest,” and union-find keeps the current friend groups without repeatedly traversing the graph.

The implementation is short because the state is simple: how many connected components remain. Once that count reaches one, the timestamp that caused it is the answer.