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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <set>
6#include <string>
7using namespace std;
8
9void dfs(const string &email, unordered_map<string, unordered_set<string>> &emailGraph,
10 unordered_set<string> &visited, vector<string> &component) {
11 visited.insert(email);
12 component.push_back(email);
13 for (const string &neighbor : emailGraph[email]) {
14 if (!visited.count(neighbor)) {
15 dfs(neighbor, emailGraph, visited, component);
16 }
17 }
18}
19
20vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
21 unordered_map<string, unordered_set<string>> emailGraph;
22 unordered_map<string, string> emailToName;
23
24 // Build the graph
25 for (const auto &account : accounts) {
26 const string &name = account[0];
27 for (int j = 1; j < account.size(); ++j) {
28 emailGraph[account[1]].insert(account[j]);
29 emailGraph[account[j]].insert(account[1]);
30 emailToName[account[j]] = name;
31 }
32 }
33
34 // DFS to find connected components
35 unordered_set<string> visited;
36 vector<vector<string>> result;
37 for (const auto &pair : emailGraph) {
38 const string &email = pair.first;
39 if (!visited.count(email)) {
40 vector<string> component;
41 dfs(email, emailGraph, visited, component);
42 sort(component.begin(), component.end());
43 component.insert(component.begin(), emailToName[email]);
44 result.push_back(component);
45 }
46 }
47 return result;
48}In this C++ solution, a graph is constructed using an unordered_map to label each email and its connections. The process involves traversing the graph with a DFS to find interconnected emails, then sorting them.
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.
1import java.util.*;
2
3
In the Java solution, Union-Find is used to connect and find associated emails. We first store each email with its own parent, then use the find operation to determine shared components. Finally, a mapping between connected components and their parent node helps in gathering and sorting emails accordingly.