Merge Contact Lists That Share an Email
Solve this ProblemYou are given several contact lists, each a list of email codes. Two lists that share at least one code belong to the same person, and the relation is transitive: if list A shares a code with B and B with C, all three are one person. Merge the lists of every person into one sorted list of codes, and return the lists ordered by their smallest code.
Treating every list as a node and joining lists that share a code gives a graph; its connected components are the persons. Union-find finds them efficiently.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ accounts.length ≤ 8; accounts[i] lists the email codes (integers 1 … 40) of the i-th account, 1 to 5 distinct codes per account (adjacency-list form of an account → email list) - ◆
Two accounts belong to the same person if they have at least one email code in common (directly, or through other accounts): the relation is transitive - ◆
A code always belongs to one person (accounts of different people never share a code) - ◆
Return one list per person containing all of their email codes in increasing order, with the lists ordered by their first (smallest) code
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Merging Any Two Lists That Overlap
BruteTreat every account as a set of email codes. Look for two sets that share a code; when you find such a pair, merge them into one set and start looking again from the beginning, because the merged set may now overlap with others. Stop when no two sets overlap. Then sort each set and sort the sets by their smallest code. Each search compares all pairs and every merge triggers a new search.
O(k³ · m)O(k · m)1class Solution {
2 public List<List<Integer>> mergeAccounts(int[][] accounts) {
3 List<TreeSet<Integer>> groups = new ArrayList<>();
4 for (int[] account : accounts) {
5 TreeSet<Integer> emails = new TreeSet<>();
6 for (int e : account) emails.add(e);
7 groups.add(emails);
8 }
9 boolean merged = true;
10 while (merged) {
11 merged = false;
12 outer:
13 for (int i = 0; i < groups.size(); i++) {
14 for (int j = i + 1; j < groups.size(); j++) {
15 for (int e : groups.get(j)) {
16 if (groups.get(i).contains(e)) {
17 groups.get(i).addAll(groups.get(j));
18 groups.remove(j);
19 merged = true;
20 break outer;
21 }
22 }
23 }
24 }
25 }
26 groups.sort(Comparator.comparingInt(TreeSet::first));
27 List<List<Integer>> result = new ArrayList<>();
28 for (TreeSet<Integer> group : groups) result.add(new ArrayList<>(group));
29 return result;
30 }
31}Optimal — Union-Find on the Accounts
OptimalRemember for every email code the first account that has it (owner). Walk through the accounts and their codes: when a code already has an owner, the current account and the owner are the same person, so union them in a union-find structure over the accounts. Afterwards go through the codes 1 … 40 in increasing order; each existing code is appended to the list of its person (the root of its owner's group), creating that list the first time the person appears. Because the codes are visited in increasing order, every list is already sorted and the lists appear ordered by their smallest code.
O(k · m · α(k) + E)O(k + E)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public List<List<Integer>> mergeAccounts(int[][] accounts) {
11 int k = accounts.length;
12 int[] parent = new int[k];
13 for (int i = 0; i < k; i++) parent[i] = i;
14 int[] owner = new int[41];
15 Arrays.fill(owner, -1);
16 for (int i = 0; i < k; i++) {
17 for (int e : accounts[i]) {
18 if (owner[e] == -1) {
19 owner[e] = i;
20 } else {
21 parent[find(parent, i)] = find(parent, owner[e]);
22 }
23 }
24 }
25 int[] groupOf = new int[k];
26 Arrays.fill(groupOf, -1);
27 List<List<Integer>> result = new ArrayList<>();
28 for (int e = 1; e <= 40; e++) {
29 if (owner[e] == -1) continue;
30 int root = find(parent, owner[e]);
31 if (groupOf[root] == -1) {
32 groupOf[root] = result.size();
33 result.add(new ArrayList<>());
34 }
35 result.get(groupOf[root]).add(e);
36 }
37 return result;
38 }
39}