LeetCode 721: Accounts Merge (Union-Find over Emails)
LeetCode 721Union-FindGraphToday we solve LeetCode 721 - Accounts Merge.
Source: https://leetcode.com/problems/accounts-merge/
English
Problem Summary
Each account has a name and multiple emails. Accounts with at least one shared email belong to the same person. Merge them and output each merged account as [name, sorted_emails...].
Key Insight
Treat each email as a node. Emails appearing in the same account are connected, so we can union them. After processing all accounts, each connected component is one merged person.
Algorithm
For every account, union its first email with all other emails in that account. Map each email to the owner's name. Then group emails by DSU root, sort each group, and prepend the corresponding name.
Complexity Analysis
Let E be total number of emails and K be max emails in one account.
Time: roughly O(E α(E) + E log E) (union/find + per-group sorting).
Space: O(E).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static class DSU {
int[] p, r;
DSU(int n) {
p = new int[n];
r = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (r[ra] < r[rb]) p[ra] = rb;
else if (r[ra] > r[rb]) p[rb] = ra;
else { p[rb] = ra; r[ra]++; }
}
}
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> id = new HashMap<>();
Map<String, String> owner = new HashMap<>();
int idx = 0;
for (List<String> acc : accounts) {
String name = acc.get(0);
for (int i = 1; i < acc.size(); i++) {
String email = acc.get(i);
if (!id.containsKey(email)) id.put(email, idx++);
owner.put(email, name);
}
}
DSU dsu = new DSU(idx);
for (List<String> acc : accounts) {
if (acc.size() <= 2) continue;
int first = id.get(acc.get(1));
for (int i = 2; i < acc.size(); i++) {
dsu.union(first, id.get(acc.get(i)));
}
}
Map<Integer, List<String>> groups = new HashMap<>();
for (String email : id.keySet()) {
int root = dsu.find(id.get(email));
groups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
}
List<List<String>> ans = new ArrayList<>();
for (List<String> emails : groups.values()) {
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(owner.get(emails.get(0)));
row.addAll(emails);
ans.add(row);
}
return ans;
}
}func accountsMerge(accounts [][]string) [][]string {
emailToID := map[string]int{}
owner := map[string]string{}
id := 0
for _, acc := range accounts {
name := acc[0]
for i := 1; i < len(acc); i++ {
email := acc[i]
if _, ok := emailToID[email]; !ok {
emailToID[email] = id
id++
}
owner[email] = name
}
}
parent := make([]int, id)
rank := make([]int, id)
for i := range parent {
parent[i] = i
}
var find func(int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
union := func(a, b int) {
ra, rb := find(a), find(b)
if ra == rb {
return
}
if rank[ra] < rank[rb] {
parent[ra] = rb
} else if rank[ra] > rank[rb] {
parent[rb] = ra
} else {
parent[rb] = ra
rank[ra]++
}
}
for _, acc := range accounts {
if len(acc) <= 2 {
continue
}
first := emailToID[acc[1]]
for i := 2; i < len(acc); i++ {
union(first, emailToID[acc[i]])
}
}
groups := map[int][]string{}
for email, i := range emailToID {
root := find(i)
groups[root] = append(groups[root], email)
}
res := make([][]string, 0, len(groups))
for _, emails := range groups {
slices.Sort(emails)
row := make([]string, 0, len(emails)+1)
row = append(row, owner[emails[0]])
row = append(row, emails...)
res = append(res, row)
}
return res
}class Solution {
public:
vector<int> p, r;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (r[ra] < r[rb]) p[ra] = rb;
else if (r[ra] > r[rb]) p[rb] = ra;
else { p[rb] = ra; r[ra]++; }
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
unordered_map<string, int> id;
unordered_map<string, string> owner;
int idx = 0;
for (auto& acc : accounts) {
string name = acc[0];
for (int i = 1; i < (int)acc.size(); i++) {
if (!id.count(acc[i])) id[acc[i]] = idx++;
owner[acc[i]] = name;
}
}
p.resize(idx);
r.assign(idx, 0);
iota(p.begin(), p.end(), 0);
for (auto& acc : accounts) {
if (acc.size() <= 2) continue;
int first = id[acc[1]];
for (int i = 2; i < (int)acc.size(); i++) {
unite(first, id[acc[i]]);
}
}
unordered_map<int, vector<string>> groups;
for (auto& [email, i] : id) {
groups[find(i)].push_back(email);
}
vector<vector<string>> ans;
for (auto& [root, emails] : groups) {
sort(emails.begin(), emails.end());
vector<string> row;
row.push_back(owner[emails[0]]);
row.insert(row.end(), emails.begin(), emails.end());
ans.push_back(move(row));
}
return ans;
}
};from collections import defaultdict
from typing import List
class DSU:
def __init__(self, n: int):
self.p = list(range(n))
self.r = [0] * n
def find(self, x: int) -> int:
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a: int, b: int) -> None:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return
if self.r[ra] < self.r[rb]:
self.p[ra] = rb
elif self.r[ra] > self.r[rb]:
self.p[rb] = ra
else:
self.p[rb] = ra
self.r[ra] += 1
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
email_to_id = {}
owner = {}
idx = 0
for acc in accounts:
name = acc[0]
for email in acc[1:]:
if email not in email_to_id:
email_to_id[email] = idx
idx += 1
owner[email] = name
dsu = DSU(idx)
for acc in accounts:
if len(acc) <= 2:
continue
first = email_to_id[acc[1]]
for email in acc[2:]:
dsu.union(first, email_to_id[email])
groups = defaultdict(list)
for email, i in email_to_id.items():
groups[dsu.find(i)].append(email)
ans = []
for emails in groups.values():
emails.sort()
ans.append([owner[emails[0]]] + emails)
return ansclass DSU {
constructor(n) {
this.p = Array.from({ length: n }, (_, i) => i);
this.r = Array(n).fill(0);
}
find(x) {
if (this.p[x] !== x) this.p[x] = this.find(this.p[x]);
return this.p[x];
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return;
if (this.r[ra] < this.r[rb]) this.p[ra] = rb;
else if (this.r[ra] > this.r[rb]) this.p[rb] = ra;
else {
this.p[rb] = ra;
this.r[ra]++;
}
}
}
var accountsMerge = function(accounts) {
const emailToId = new Map();
const owner = new Map();
let id = 0;
for (const acc of accounts) {
const name = acc[0];
for (let i = 1; i < acc.length; i++) {
const email = acc[i];
if (!emailToId.has(email)) emailToId.set(email, id++);
owner.set(email, name);
}
}
const dsu = new DSU(id);
for (const acc of accounts) {
if (acc.length <= 2) continue;
const first = emailToId.get(acc[1]);
for (let i = 2; i < acc.length; i++) {
dsu.union(first, emailToId.get(acc[i]));
}
}
const groups = new Map();
for (const [email, i] of emailToId.entries()) {
const root = dsu.find(i);
if (!groups.has(root)) groups.set(root, []);
groups.get(root).push(email);
}
const ans = [];
for (const emails of groups.values()) {
emails.sort();
ans.push([owner.get(emails[0]), ...emails]);
}
return ans;
};中文
题目总结
每个账户包含用户名和多个邮箱。只要两个账户共享任意一个邮箱，就属于同一个人。最终输出合并后的账户：[name, 排序后的所有邮箱...]。
核心思路
把邮箱当成图里的节点。同一账户内邮箱两两连通，可以用并查集（Union-Find）维护连通分量。每个连通分量就是一个合并后的账户。
算法步骤
先给每个邮箱分配整数 id，并记录邮箱到用户名映射。然后在同一账户内把第一个邮箱和其余邮箱做 union。最后按根节点分组、组内排序邮箱，并在最前面加上用户名。
复杂度分析
设邮箱总数为 E。
时间复杂度约为 O(E α(E) + E log E)（并查集合并/查找 + 分组排序）。
空间复杂度 O(E)。
参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static class DSU {
int[] p, r;
DSU(int n) {
p = new int[n];
r = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (r[ra] < r[rb]) p[ra] = rb;
else if (r[ra] > r[rb]) p[rb] = ra;
else { p[rb] = ra; r[ra]++; }
}
}
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> id = new HashMap<>();
Map<String, String> owner = new HashMap<>();
int idx = 0;
for (List<String> acc : accounts) {
String name = acc.get(0);
for (int i = 1; i < acc.size(); i++) {
String email = acc.get(i);
if (!id.containsKey(email)) id.put(email, idx++);
owner.put(email, name);
}
}
DSU dsu = new DSU(idx);
for (List<String> acc : accounts) {
if (acc.size() <= 2) continue;
int first = id.get(acc.get(1));
for (int i = 2; i < acc.size(); i++) {
dsu.union(first, id.get(acc.get(i)));
}
}
Map<Integer, List<String>> groups = new HashMap<>();
for (String email : id.keySet()) {
int root = dsu.find(id.get(email));
groups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
}
List<List<String>> ans = new ArrayList<>();
for (List<String> emails : groups.values()) {
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(owner.get(emails.get(0)));
row.addAll(emails);
ans.add(row);
}
return ans;
}
}func accountsMerge(accounts [][]string) [][]string {
emailToID := map[string]int{}
owner := map[string]string{}
id := 0
for _, acc := range accounts {
name := acc[0]
for i := 1; i < len(acc); i++ {
email := acc[i]
if _, ok := emailToID[email]; !ok {
emailToID[email] = id
id++
}
owner[email] = name
}
}
parent := make([]int, id)
rank := make([]int, id)
for i := range parent {
parent[i] = i
}
var find func(int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
union := func(a, b int) {
ra, rb := find(a), find(b)
if ra == rb {
return
}
if rank[ra] < rank[rb] {
parent[ra] = rb
} else if rank[ra] > rank[rb] {
parent[rb] = ra
} else {
parent[rb] = ra
rank[ra]++
}
}
for _, acc := range accounts {
if len(acc) <= 2 {
continue
}
first := emailToID[acc[1]]
for i := 2; i < len(acc); i++ {
union(first, emailToID[acc[i]])
}
}
groups := map[int][]string{}
for email, i := range emailToID {
root := find(i)
groups[root] = append(groups[root], email)
}
res := make([][]string, 0, len(groups))
for _, emails := range groups {
slices.Sort(emails)
row := make([]string, 0, len(emails)+1)
row = append(row, owner[emails[0]])
row = append(row, emails...)
res = append(res, row)
}
return res
}class Solution {
public:
vector<int> p, r;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (r[ra] < r[rb]) p[ra] = rb;
else if (r[ra] > r[rb]) p[rb] = ra;
else { p[rb] = ra; r[ra]++; }
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
unordered_map<string, int> id;
unordered_map<string, string> owner;
int idx = 0;
for (auto& acc : accounts) {
string name = acc[0];
for (int i = 1; i < (int)acc.size(); i++) {
if (!id.count(acc[i])) id[acc[i]] = idx++;
owner[acc[i]] = name;
}
}
p.resize(idx);
r.assign(idx, 0);
iota(p.begin(), p.end(), 0);
for (auto& acc : accounts) {
if (acc.size() <= 2) continue;
int first = id[acc[1]];
for (int i = 2; i < (int)acc.size(); i++) {
unite(first, id[acc[i]]);
}
}
unordered_map<int, vector<string>> groups;
for (auto& [email, i] : id) {
groups[find(i)].push_back(email);
}
vector<vector<string>> ans;
for (auto& [root, emails] : groups) {
sort(emails.begin(), emails.end());
vector<string> row;
row.push_back(owner[emails[0]]);
row.insert(row.end(), emails.begin(), emails.end());
ans.push_back(move(row));
}
return ans;
}
};from collections import defaultdict
from typing import List
class DSU:
def __init__(self, n: int):
self.p = list(range(n))
self.r = [0] * n
def find(self, x: int) -> int:
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a: int, b: int) -> None:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return
if self.r[ra] < self.r[rb]:
self.p[ra] = rb
elif self.r[ra] > self.r[rb]:
self.p[rb] = ra
else:
self.p[rb] = ra
self.r[ra] += 1
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
email_to_id = {}
owner = {}
idx = 0
for acc in accounts:
name = acc[0]
for email in acc[1:]:
if email not in email_to_id:
email_to_id[email] = idx
idx += 1
owner[email] = name
dsu = DSU(idx)
for acc in accounts:
if len(acc) <= 2:
continue
first = email_to_id[acc[1]]
for email in acc[2:]:
dsu.union(first, email_to_id[email])
groups = defaultdict(list)
for email, i in email_to_id.items():
groups[dsu.find(i)].append(email)
ans = []
for emails in groups.values():
emails.sort()
ans.append([owner[emails[0]]] + emails)
return ansclass DSU {
constructor(n) {
this.p = Array.from({ length: n }, (_, i) => i);
this.r = Array(n).fill(0);
}
find(x) {
if (this.p[x] !== x) this.p[x] = this.find(this.p[x]);
return this.p[x];
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return;
if (this.r[ra] < this.r[rb]) this.p[ra] = rb;
else if (this.r[ra] > this.r[rb]) this.p[rb] = ra;
else {
this.p[rb] = ra;
this.r[ra]++;
}
}
}
var accountsMerge = function(accounts) {
const emailToId = new Map();
const owner = new Map();
let id = 0;
for (const acc of accounts) {
const name = acc[0];
for (let i = 1; i < acc.length; i++) {
const email = acc[i];
if (!emailToId.has(email)) emailToId.set(email, id++);
owner.set(email, name);
}
}
const dsu = new DSU(id);
for (const acc of accounts) {
if (acc.length <= 2) continue;
const first = emailToId.get(acc[1]);
for (let i = 2; i < acc.length; i++) {
dsu.union(first, emailToId.get(acc[i]));
}
}
const groups = new Map();
for (const [email, i] of emailToId.entries()) {
const root = dsu.find(i);
if (!groups.has(root)) groups.set(root, []);
groups.get(root).push(email);
}
const ans = [];
for (const emails of groups.values()) {
emails.sort();
ans.push([owner.get(emails[0]), ...emails]);
}
return ans;
};
Comments