Definition
- Union-Find – each distinct email gets an integer ID; emails within the same account row are unioned together.
- Transitive merging – if account A and account B share an email, and B and C share another, all three accounts merge into one.
- Grouping – after all unions, emails are grouped by their root; each group becomes one merged account.
- Identity key – emails, not names, determine identity; two people can share a name but not a verified email.
- Output – each merged account has the name and a sorted list of unique emails.
National Bank of India sometimes has the same customer registered under multiple profiles that share an email. If profile A and profile B share one email, they are the same person. If B and C share another email, then A, B, and C are all one person. You link shared emails, then gather every email under the same head into one clean profile.
Understanding the Concepts
What is the Accounts Merge problem?
Given a list of accounts where each account is a name followed by one or more emails, merge accounts that share any email. Return merged accounts with the name and sorted unique emails.
At the National Bank of India, a single customer like Rajesh may have registered multiple profiles that share a verified email. The master data system needs one golden record per real person.
package com.bank.identity;
import java.util.*;
public class AccountsMergeDemo {
public static void main(String[] args) {
List<List<String>> accounts = List.of(
List.of("Rajesh", "rajesh@bank.in", "rajesh@gmail.com"),
List.of("Priya", "priya@bank.in"),
List.of("Rajesh", "rajesh@work.in", "rajesh@gmail.com")
);
List<List<String>> merged = accountsMerge(accounts);
merged.forEach(System.out::println);
}
// implementation below
}
[Rajesh, rajesh@bank.in, rajesh@gmail.com, rajesh@work.in]
[Priya, priya@bank.in]
How does Union-Find solve this?
Assign each first-seen email a unique integer ID. For each account row, union the first email's ID with every other email's ID. This makes all emails within one account share a root. Because union is transitive, two accounts that share an email will have their emails linked into the same set.
package com.bank.identity;
import java.util.*;
public class AccountsMerge {
static int[] parent, rank;
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
static List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> emailToId = new HashMap<>();
Map<String, String> emailToName = new HashMap<>();
// Step 1: assign IDs
for (List<String> acct : accounts) {
String name = acct.get(0);
for (int i = 1; i < acct.size(); i++) {
String email = acct.get(i);
emailToId.putIfAbsent(email, emailToId.size());
emailToName.put(email, name);
}
}
// Step 2: init Union-Find
int n = emailToId.size();
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
// Step 3: union emails within each account
for (List<String> acct : accounts) {
int firstId = emailToId.get(acct.get(1));
for (int i = 2; i < acct.size(); i++) {
union(firstId, emailToId.get(acct.get(i)));
}
}
// Step 4: group by root
Map<Integer, List<String>> groups = new HashMap<>();
for (Map.Entry<String, Integer> entry : emailToId.entrySet()) {
int root = find(entry.getValue());
groups.computeIfAbsent(root, k -> new ArrayList<>()).add(entry.getKey());
}
// Step 5: build result
List<List<String>> result = new ArrayList<>();
for (List<String> emails : groups.values()) {
Collections.sort(emails);
String name = emailToName.get(emails.get(0));
List<String> merged = new ArrayList<>();
merged.add(name);
merged.addAll(emails);
result.add(merged);
}
return result;
}
}
Why are emails the identity key, not names?
Two different customers can have the same name, but a verified email belongs to exactly one person. Unioning on names would incorrectly merge distinct people who happen to share a name.
// WRONG: merging by name
// "Rajesh" with rajesh@bank.in
// "Rajesh" with rajesh@other.in (different person!)
// Merging by name would fuse them incorrectly.
// CORRECT: merging by shared email
// Only accounts that share at least one email are the same person.
How does transitivity work?
If account A has emails {e1, e2} and account B has emails {e2, e3}, they share e2 so they merge into {e1, e2, e3}. If account C has {e3, e4}, it shares e3 with the merged set, so all three become {e1, e2, e3, e4}.
package com.bank.identity;
import java.util.List;
public class TransitiveExample {
public static void main(String[] args) {
List<List<String>> accounts = List.of(
List.of("Rajesh", "e1@bank.in", "e2@bank.in"),
List.of("Rajesh", "e2@bank.in", "e3@bank.in"),
List.of("Rajesh", "e3@bank.in", "e4@bank.in")
);
// After union: e1, e2, e3, e4 all share one root
// Result: [Rajesh, e1@bank.in, e2@bank.in, e3@bank.in, e4@bank.in]
AccountsMerge.accountsMerge(accounts).forEach(System.out::println);
}
}
[Rajesh, e1@bank.in, e2@bank.in, e3@bank.in, e4@bank.in]
What is the time and space complexity?
The time is dominated by sorting the emails within each group, which is O(E log E) where E is the total number of emails. The union operations with path compression and rank are nearly constant, O(alpha(E)) per operation.
| Step | Time |
|------|------|
| Assign IDs | O(E) |
| Union | O(E * alpha(E)) |
| Group by root | O(E) |
| Sort groups | O(E log E) |
| Total | O(E log E) |
What are the edge cases?
Edge cases include accounts with only one email (nothing to union), all accounts being the same person, and no shared emails at all.
// Edge: all separate
List.of(
List.of("A", "a@x.com"),
List.of("B", "b@x.com"),
List.of("C", "c@x.com")
);
// Result: three separate accounts
// Edge: all one person
List.of(
List.of("A", "a@x.com", "b@x.com"),
List.of("A", "b@x.com", "c@x.com")
);
// Result: one account with a, b, c
What are common mistakes?
The most common mistake is merging by name instead of by shared email. Another is forgetting to sort the emails in the output.
// WRONG: using name as the merge key
Map<String, Set<String>> byName = new HashMap<>();
for (List<String> acct : accounts) {
byName.computeIfAbsent(acct.get(0), k -> new HashSet<>())
.addAll(acct.subList(1, acct.size()));
}
// This merges ALL accounts with the same name, even if they are different people!
// CORRECT: use Union-Find on emails
// Only accounts sharing an email get merged
What should a senior engineer know?
- Path compression + union by rank. Together these make Union-Find nearly O(1) per operation. Always implement both for interview-grade code.
- DFS alternative. Build a graph where each email is a node and edges connect emails within the same account. Run DFS/BFS from each unvisited email to find connected components. Same result, different data structure.
- Production deduplication. In real master data management, email matching is one signal among many (phone, address, name similarity). But the Union-Find pattern remains the core merge engine.
- Idempotency. Running the merge multiple times on the same input produces the same result, which is important for batch pipelines that may retry.
Visual Overview
Input accounts:
[Rajesh, rajesh@bank.in, rajesh@gmail.com]
[Priya, priya@bank.in]
[Rajesh, rajesh@work.in, rajesh@gmail.com]
Email IDs:
rajesh@bank.in -> 0
rajesh@gmail.com -> 1
priya@bank.in -> 2
rajesh@work.in -> 3
Unions:
Account 1: union(0, 1) -> {0, 1}
Account 2: (no union, single email)
Account 3: union(3, 1) -> {0, 1, 3}
Groups by root:
Root 0: [rajesh@bank.in, rajesh@gmail.com, rajesh@work.in]
Root 2: [priya@bank.in]
Output:
[Rajesh, rajesh@bank.in, rajesh@gmail.com, rajesh@work.in]
[Priya, priya@bank.in]
Key Takeaway
Accounts Merge is a Union-Find problem where the identity key is the email, not the name. I give every distinct email a unique integer ID and record which name owns it. For each account row, I union the first email's ID with every other email's ID, making all emails of a single profile share one root. Because unions are transitive, two profiles that share an email with a third profile all collapse into one set.
To produce the output, I group every email by its Union-Find root, sort the emails within each group, and prepend the owner's name. Sorting dominates the cost at O(E log E), while the union operations are nearly constant with path compression and union by rank.
The critical insight is that emails, not names, are the merge key. Two different customers can share a name but never a verified email, so unioning on names would incorrectly fuse distinct people. At the National Bank of India, the master data system used this exact pattern to deduplicate customer profiles, producing one golden record per real person with all associated emails listed once in sorted order.
Remember one sentence: union emails within each account row using Union-Find, group by root, sort each group, and the result is one merged account per real person.
---