A billing identity service merges CRM rows that look like [name, email, email, ...]. Two rows are one person when any address overlaps; the display name is only a label. The intern built an undirected graph of every email and DFS’d from each unvisited address. Two hundred contacts in staging returned. Ten thousand production accounts, some with a dozen aliases, were still allocating neighbor lists when the request timed out.
Accounts Merge asks you to union accounts that share an email, then emit one row per leftover person with emails sorted. Same leftover components as Number of Provinces — that prompt unions integer city ids on a matrix. Here the keys are strings, so a hash table maps each email onto an account index first. This is an interview writeup, not a layout lecture. The graphs post owns adjacency. The union-find post owns path compression and rank. Here we only union account ids that share a key, then group emails per root.
The problem
Given a list of accounts, each row is [name, email1, email2, ...]. Merge every group of rows that belong to the same person. Two accounts are the same person when they share at least one email; sharing is transitive. Return the merged rows: the name preserved, emails unique and sorted. Order of the rows does not matter.
John johnsmith@mail.com john_newyork@mail.com
John johnsmith@mail.com john00@mail.com
Mary mary@mail.com
John johnnybravo@mail.com
→
John john00@mail.com john_newyork@mail.com johnsmith@mail.com
Mary mary@mail.com
John johnnybravo@mail.com
John a@x.com b@x.com
John b@x.com c@x.com
John c@x.com d@x.com
→ John a@x.com b@x.com c@x.com d@x.comFirst block: the first two Johns share johnsmith@mail.com, so they merge; johnnybravo@mail.com does not overlap. Second: a three-account chain is still one person.
Note: The same display name does not merge two rows. Two Johns with disjoint emails stay two people. The name on a merged row can come from any account in the component.
An email graph plus DFS is the honest brute force
Treat emails as vertices. Inside one account, connect consecutive addresses so that row is a path. DFS each unvisited email, collect the component, attach the name, sort. Correct. You stored a neighbor list of strings when the vertices you actually merge are accounts.
A clique among the emails in a row is extra edges, not extra insight. An unmarked walk on those undirected edges bounces; mark inside the flood.
List<List<String>> accountsMergeGraph(List<List<String>> accounts) {
Map<String, List<String>> adj = new HashMap<>();
Map<String, String> emailToName = new HashMap<>();
for (List<String> acc : accounts) {
String name = acc.get(0);
for (int j = 1; j < acc.size(); j++) {
String email = acc.get(j);
emailToName.put(email, name);
adj.putIfAbsent(email, new ArrayList<>());
if (j > 1) {
String prev = acc.get(j - 1);
adj.get(prev).add(email);
adj.get(email).add(prev);
}
}
}
Set<String> seen = new HashSet<>();
List<List<String>> merged = new ArrayList<>();
for (String email : adj.keySet()) {
if (seen.contains(email)) {
continue;
}
List<String> emails = new ArrayList<>();
collect(email, adj, seen, emails);
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(emailToName.get(emails.get(0)));
row.addAll(emails);
merged.add(row);
}
return merged;
}
void collect(String email, Map<String, List<String>> adj, Set<String> seen, List<String> emails) {
if (!seen.add(email)) {
return;
}
emails.add(email);
for (String nei : adj.get(email)) {
collect(nei, adj, seen, emails);
}
}At a dozen contacts this is a rounding error. On thousands of aliases you paid an adjacency list per address for a question that only needs one union per shared key: which account ids already own this email?
Map each email onto an account id, then union
One parent array of length n — the accounts, not the emails. Each account starts as its own root. A map email → first account index that listed it.
For each account i, for each email: miss means record email → i; hit means union(i, owner). Same root is already one person — skip. Then walk the map once: find the owner, dump the email into that root’s list, sort each list, prepend the root row’s name. Flatten-on-find and rank live in the union-find post; do not re-lecture them at this board unless they ask.
0 John a@x.com b@x.com
1 John a@x.com c@x.com
2 Mary m@x.com
3 John d@x.com
email→id
a@x.com → 0
b@x.com → 0
a@x.com already 0, union(1, 0) parent[1]=0
c@x.com → 1
m@x.com → 2
d@x.com → 3
emails by find(id)
root 0: a@x.com, b@x.com, c@x.com
root 2: m@x.com
root 3: d@x.com
sort each group, name from the root rowThe Java is that map-and-union. find and union are the same helpers as Number of Provinces; the map is the only extra because the keys are strings.
List<List<String>> accountsMerge(List<List<String>> accounts) {
int n = accounts.size();
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
Map<String, Integer> emailToId = new HashMap<>();
for (int i = 0; i < n; i++) {
List<String> acc = accounts.get(i);
for (int j = 1; j < acc.size(); j++) {
String email = acc.get(j);
Integer owner = emailToId.get(email);
if (owner == null) {
emailToId.put(email, i);
} else {
union(parent, i, owner);
}
}
}
Map<Integer, List<String>> emailsByRoot = new HashMap<>();
for (Map.Entry<String, Integer> e : emailToId.entrySet()) {
int root = find(parent, e.getValue());
List<String> emails = emailsByRoot.get(root);
if (emails == null) {
emails = new ArrayList<>();
emailsByRoot.put(root, emails);
}
emails.add(e.getKey());
}
List<List<String>> merged = new ArrayList<>();
for (Map.Entry<Integer, List<String>> e : emailsByRoot.entrySet()) {
List<String> emails = e.getValue();
Collections.sort(emails);
List<String> row = new ArrayList<>();
row.add(accounts.get(e.getKey()).get(0));
row.addAll(emails);
merged.add(row);
}
return merged;
}
int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
boolean union(int[] parent, int a, int b) {
int ra = find(parent, a);
int rb = find(parent, b);
if (ra == rb) {
return false;
}
parent[ra] = rb;
return true;
}Time is expected O(k α(n) + k log k) — one map operation per email occurrence k, nearly-constant unions, then a sort of each group’s addresses. Space is O(n + k) for parent and the email map. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.
Note: Union account indices, not the name string. The map’s values are 0 … n-1. Copying every email into Map<String, List<String>> adj is the brute’s extra storage, not extra insight.
What interviewers usually poke next
- Number of Provinces. Same leftover components; the matrix already had integer ids. Here you map strings onto
0 … n-1first. - DFS / BFS on the email graph. Persistent
seenset. Iterative flood uses anArrayDeque, notjava.util.Stack, notArrayList.remove(0). - Union emails as vertices. Map each distinct email onto
0 … U-1and union those ints. Same structure; more ids thannwhen accounts have many aliases. - Rank, or a read-only find. The union-find post owns those tweaks. Name them; do not derive them here unless they ask.
- One account, or disjoint Johns. A single row returns itself with emails sorted. Same name, no shared email: two rows.
You are done with this problem when you can say, out loud, why an email neighbor list is extra adjacency, why the same display name does not merge, and why leftover roots after unioning shared keys are the people.