Sponsored
Sponsored
In this approach, we treat each email as a node in a graph and create edges between nodes that appear in the same account. By doing so, connected components in the graph will represent emails belonging to the same person.
Once the graph is constructed, we perform a Depth-First Search (DFS) to enumerate all emails in each connected component, sort the collected emails, and then append the owner’s name to produce the final result.
Time complexity is O(NK log NK), where N is the number of accounts, and K is the maximum number of emails in an account, due to sorting each component. Space complexity is O(NK) for storing the graph and visited nodes.
1from collections import defaultdict
2
3def accountsMerge(accounts):
4 email_graph = defaultdict(set)
5 email_to_name = {}
6
7 for account in accounts:
8 name = account[0]
9 emails = account[1:]
10 first_email = emails[0]
11
12 for email in emails:
13 email_graph[first_email].add(email)
14 email_graph[email].add(first_email)
15 email_to_name[email] = name
16
17 visited = set()
18 def dfs(email):
19 visited.add(email)
20 component = [email]
21 for neighbor in email_graph[email]:
22 if neighbor not in visited:
23 component.extend(dfs(neighbor))
24 return component
25
26 output = []
27 for email in email_graph:
28 if email not in visited:
29 connected_emails = dfs(email)
30 output.append([email_to_name[email]] + sorted(connected_emails))
31
32 return outputThe Python solution uses a dictionary to map emails to a graph structure. Each email is treated as a node, and accounts describe connections. We apply a depth-first search to explore connected components and collect emails of each component. Each collection is sorted and paired with the account owner’s name before appending to the result list.
This approach uses a Union-Find data structure for efficient merging of accounts. Each email is identified with a parent, initially itself, and accounts are unified if they share an email. We then deduce separate email sets from parent-child relationships.
Time complexity is O(NK log NK) due to sorting each email list. Space complexity is O(NK) owing to email mappings and Union-Find arrangements.
1var accountsMerge = function(accounts) {
2
The JavaScript solution leverages an object for Union-Find representation. After creating initial email relations, emails are unified under a common parent, gathered to generate connected components, which are finally sorted for the output.