Each entry of accounts is a list [name, email1, email2, ...]. Two accounts belong to the same person if they share any email, and this is transitive: if A shares an email with B and B shares one with C, all three are one person. Accounts that share an email always have the same name, but different people can have the same name.
Write accounts_merge(accounts) -> list[list[str]] that merges accounts belonging to the same person. Each merged account is [name, *emails] with the emails sorted (plain string order) and without duplicates. The merged accounts themselves may be returned in any order.
accounts_merge([
["Ana", "[email protected]", "[email protected]"],
["Bo", "[email protected]"],
["Ana", "[email protected]", "[email protected]"],
["Ana", "[email protected]"],
])
# [["Ana", "[email protected]", "[email protected]", "[email protected]"], ["Bo", "[email protected]"], ["Ana", "[email protected]"]]
Constraints: 1 <= len(accounts) <= 20_000, each account has a name and 1 to 10 emails, and every name and email is at most 30 characters. The tests include 20,000 accounts linked in one long chain, where repeatedly merging pairs of lists until nothing changes is far too slow; aim for near-linear time (plus sorting).
Show hint
treat emails as nodes and let each account connect all of its emails. The people are then the connected groups of emails.