Why it works
- Accounts are the items of the union-find. owner keeps the first account of every email, so an email seen again links the account to that first one, and links never break.
- Joining is catching: account 2 meets account 1, which is already under account 0, so all three end up under one root without account 2 ever meeting account 0.
- Grouping by the root of each account puts every email of a person in one place; the set drops the repeats, and only the name is taken from the account.
Complexity
Time O(E · h + E log E) for E emails in all: up to two finds per email, as deep as the trees (up to the number of accounts here, almost a constant with re-hanging on the root and the smaller tree under the bigger), and the sort. Memory O(E) for owner and groups.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗