#721
Accounts Merge
Medium Union-Find on emails
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each account is a name followed by emails. Two accounts belong to the same person if they share any email. Merge them and return each person's name with their sorted emails.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: merge accounts that share any email.
Why this works: union all emails inside each account; emails with the same root belong to one person.
Example: John [a, b], John [b, c], John [d]
a-b-c connected → one accountd alone → another account
✦Hints open one at a time
Union all emails within one account.
Map each email to an id and remember one owner name per email.
Group emails by their root, then sort each group.
↗Approach
Give each new email an index; union every email of an account with the account's first email. Then collect emails per root in a map, sort them, and prepend the name.
</>Solution (Java)
import java.util.*;
class Solution {
private int[] parent;
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> id = new HashMap<>();
Map<String, String> owner = new HashMap<>();
for (List<String> acc : accounts)
for (int i = 1; i < acc.size(); i++) {
id.putIfAbsent(acc.get(i), id.size());
owner.put(acc.get(i), acc.get(0));
}
parent = new int[id.size()];
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (List<String> acc : accounts) {
int first = id.get(acc.get(1));
for (int i = 2; i < acc.size(); i++) parent[find(id.get(acc.get(i)))] = find(first); // same person
}
Map<Integer, List<String>> groups = new HashMap<>();
for (String email : id.keySet()) groups.computeIfAbsent(find(id.get(email)), k -> new ArrayList<>()).add(email);
List<List<String>> res = new ArrayList<>();
for (List<String> emails : groups.values()) {
Collections.sort(emails);
emails.add(0, owner.get(emails.get(0)));
res.add(emails);
}
return res;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}!Common mistake
Merging accounts by name — different people can share a name.
Complexity
- Time: O(N log N), N = total emails (sorting dominates).
- Space: O(N).
Topic: Graphs
🎬 Episodes 74–85: video coming soon