Accounts Merge – Solution & Complexity

def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
    parent = list(range(len(accounts)))
    rank = [0] * len(accounts)

    def find(node: int) -> int:
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node

    def union(a: int, b: int) -> None:
        root_a = find(a)
        root_b = find(b)
        if root_a == root_b:
            return
        if rank[root_a] < rank[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        if rank[root_a] == rank[root_b]:
            rank[root_a] += 1

    email_owner: dict[str, int] = {}
    for index, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_owner:
                union(index, email_owner[email])
            else:
                email_owner[email] = index

    grouped: dict[int, list[str]] = {}
    for email in email_owner:
        root = find(email_owner[email])
        grouped.setdefault(root, []).append(email)

    merged: list[list[str]] = []
    for root, emails in grouped.items():
        emails.sort()
        merged.append([accounts[root][0], *emails])

    merged.sort(key=lambda row: (row[0], row[1]))
    return merged