Union-Find on emails. Group by root, then format output.
class UnionFind: def init(self): self.parent = {} def find(self, x): if x not in self.parent: self.parent[x] = x if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): self.parent[self.find(x)] = self.find(y)
def accountsMerge(accounts): uf = UnionFind() emailToName = {} for name, *emails in accounts: for email in emails: emailToName[email] = name uf.union(emails[0], email) groups = defaultdict(list) for email in emailToName: groups[uf.find(email)].append(email) return [[emailToName[root]] + sorted(emails) for root, emails in groups.items()]
time, space.