Accounts Merge

🎯

Accounts Merge

mediumGRAPHFacebookAmazonGoogle

Imagine you have multiple user accounts with overlapping email addresses, and you want to merge accounts that belong to the same person based on shared emails.

💡 This problem involves grouping related items (emails) that appear in different accounts. Beginners often struggle because it requires understanding how to efficiently merge groups and then reconstruct the merged accounts.

📋

Problem Statement

Given a list of accounts where each account is a list of strings, the first string is the name, and the rest are emails belonging to that account. Merge accounts that have at least one email in common. Return the merged accounts in the format where the first element is the name and the rest are the sorted unique emails.

1 ≤ number of accounts ≤ 10^51 ≤ number of emails per account ≤ 10^31 ≤ length of each email ≤ 30All emails contain only lowercase English letters, digits, '@' and '.'Name length ≤ 20

💡

Example

Input"[[\"John\", \"[e-mail]\", \"[e-mail]\"], [\"John\", \"[e-mail]\"], [\"John\", \"[e-mail]\", \"[e-mail]\"], [\"Mary\", \"[e-mail]\"]]"

Output[["John", "[e-mail]", "[e-mail]", "[e-mail]"], ["John", "[e-mail]"], ["Mary", "[e-mail]"]]

The first and third accounts share '[e-mail]', so they are merged. The second and fourth accounts have unique emails and remain separate.

• All accounts have completely unique emails → output is same as input but sorted emails
• All accounts share at least one email → all accounts merge into one
• An account with only one email → should be handled correctly
• Multiple accounts with the same name but no shared emails → remain separate

⚠️

Common Mistakes

Not using union-find or graph, trying to merge accounts by name only

Fails to merge accounts with same emails but different names

✅ Use emails as keys and union-find to merge accounts

Not sorting emails before output

Output order differs from expected, causing test failures

✅ Sort emails in each merged account before returning

Union emails incorrectly by not connecting all emails in an account

Partial merges cause incorrect grouping

✅ Union all emails in the same account with the first email

Using inefficient brute force approach for large inputs

Time limit exceeded or very slow runtime

✅ Use union-find or graph traversal for efficient merging

Not handling accounts with single email correctly

May miss merging or cause errors

✅ Treat single email accounts same as others in union-find

🧠

Brute Force (Nested Loops to Check Email Overlaps)

💡 This approach exists to build intuition by directly comparing every pair of accounts to find common emails, which is straightforward but inefficient.

Intuition

Check every pair of accounts to see if they share any email. If yes, merge them. Repeat until no more merges are possible.

Algorithm

1. Initialize a list to hold merged accounts.
2. For each account, compare with every other account to check if they share any email.
3. If they share emails, merge the accounts by combining their emails and names.
4. Repeat the process until no more merges occur.
5. Sort emails in each merged account and return the result.

💡 The nested loops and repeated merging make it hard to see efficiency and correctness at first.

</>

Code

from typing import List

def accountsMerge(accounts: List[List[str]]) -> List[List[str]]:
    merged = []
    used = [False] * len(accounts)

    def have_common_email(emails_set, account):
        # Check if any email in account is in emails_set
        for email in account[1:]:
            if email in emails_set:
                return True
        return False

    for i in range(len(accounts)):
        if used[i]:
            continue
        name = accounts[i][0]
        emails = set(accounts[i][1:])
        changed = True
        while changed:
            changed = False
            for j in range(i + 1, len(accounts)):
                if not used[j] and have_common_email(emails, accounts[j]):
                    emails.update(accounts[j][1:])
                    used[j] = True
                    changed = True
        used[i] = True
        merged.append([name] + sorted(emails))
    return merged

# Driver code
if __name__ == '__main__':
    input_accounts = [["John", "[e-mail]", "[e-mail]"],
                      ["John", "[e-mail]"],
                      ["John", "[e-mail]", "[e-mail]"],
                      ["Mary", "[e-mail]"]]
    print(accountsMerge(input_accounts))

Line Notes

used = [False] * len(accounts)Track which accounts have been merged to avoid duplicate processing

def have_common_email(emails_set, account):Helper function to check if current account shares any email with the merged set

for i in range(len(accounts))Iterate over each account to attempt merging with others

while changed:Repeat merging until no new merges occur in this iteration

import java.util.*;

public class AccountsMergeBrute {
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        boolean[] used = new boolean[n];
        List<List<String>> merged = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            String name = accounts.get(i).get(0);
            Set<String> emails = new HashSet<>(accounts.get(i).subList(1, accounts.get(i).size()));
            boolean changed = true;
            while (changed) {
                changed = false;
                for (int j = i + 1; j < n; j++) {
                    if (!used[j] && haveCommonEmail(emails, accounts.get(j))) {
                        emails.addAll(accounts.get(j).subList(1, accounts.get(j).size()));
                        used[j] = true;
                        changed = true;
                    }
                }
            }
            used[i] = true;
            List<String> mergedAccount = new ArrayList<>();
            mergedAccount.add(name);
            List<String> sortedEmails = new ArrayList<>(emails);
            Collections.sort(sortedEmails);
            mergedAccount.addAll(sortedEmails);
            merged.add(mergedAccount);
        }
        return merged;
    }

    private static boolean haveCommonEmail(Set<String> emails, List<String> account) {
        for (int i = 1; i < account.size(); i++) {
            if (emails.contains(account.get(i))) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("John", "[e-mail]"),
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("Mary", "[e-mail]")
        );
        System.out.println(accountsMerge(accounts));
    }
}

Line Notes

boolean[] used = new boolean[n];Keep track of accounts already merged to avoid reprocessing

while (changed) {Repeat merging until no new merges are found in this iteration

haveCommonEmail(emails, accounts.get(j))Check if current emails overlap with another account's emails

Collections.sort(sortedEmails);Sort emails before adding to final merged account for consistent output

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

bool haveCommonEmail(const set<string>& emails, const vector<string>& account) {
    for (int i = 1; i < (int)account.size(); i++) {
        if (emails.count(account[i])) return true;
    }
    return false;
}

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    int n = accounts.size();
    vector<bool> used(n, false);
    vector<vector<string>> merged;

    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        string name = accounts[i][0];
        set<string> emails(accounts[i].begin() + 1, accounts[i].end());
        bool changed = true;
        while (changed) {
            changed = false;
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && haveCommonEmail(emails, accounts[j])) {
                    emails.insert(accounts[j].begin() + 1, accounts[j].end());
                    used[j] = true;
                    changed = true;
                }
            }
        }
        used[i] = true;
        vector<string> mergedAccount;
        mergedAccount.push_back(name);
        mergedAccount.insert(mergedAccount.end(), emails.begin(), emails.end());
        sort(mergedAccount.begin() + 1, mergedAccount.end());
        merged.push_back(mergedAccount);
    }
    return merged;
}

int main() {
    vector<vector<string>> accounts = {
        {"John", "[e-mail]", "[e-mail]"},
        {"John", "[e-mail]"},
        {"John", "[e-mail]", "[e-mail]"},
        {"Mary", "[e-mail]"}
    };
    vector<vector<string>> result = accountsMerge(accounts);
    for (auto& acc : result) {
        for (auto& s : acc) cout << s << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

vector<bool> used(n, false);Track which accounts have been merged to avoid duplicates

while (changed) {Repeat merging until no new merges occur in this iteration

haveCommonEmail(emails, accounts[j])Check if two accounts share any email to decide merging

sort(mergedAccount.begin() + 1, mergedAccount.end());Sort emails before output for consistent ordering

function accountsMerge(accounts) {
    const n = accounts.length;
    const used = new Array(n).fill(false);
    const merged = [];

    function haveCommonEmail(emailsSet, account) {
        for (let i = 1; i < account.length; i++) {
            if (emailsSet.has(account[i])) return true;
        }
        return false;
    }

    for (let i = 0; i < n; i++) {
        if (used[i]) continue;
        const name = accounts[i][0];
        const emails = new Set(accounts[i].slice(1));
        let changed = true;
        while (changed) {
            changed = false;
            for (let j = i + 1; j < n; j++) {
                if (!used[j] && haveCommonEmail(emails, accounts[j])) {
                    for (let k = 1; k < accounts[j].length; k++) {
                        emails.add(accounts[j][k]);
                    }
                    used[j] = true;
                    changed = true;
                }
            }
        }
        used[i] = true;
        const mergedAccount = [name, ...Array.from(emails).sort()];
        merged.push(mergedAccount);
    }
    return merged;
}

// Driver code
const inputAccounts = [
    ["John", "[e-mail]", "[e-mail]"],
    ["John", "[e-mail]"],
    ["John", "[e-mail]", "[e-mail]"],
    ["Mary", "[e-mail]"]
];
console.log(accountsMerge(inputAccounts));

Line Notes

const used = new Array(n).fill(false);Track which accounts have been merged to avoid duplicates

while (changed) {Repeat merging until no new merges occur in this iteration

haveCommonEmail(emails, accounts[j])Check if two accounts share any email to decide merging

Array.from(emails).sort()Sort emails before adding to final merged account for consistent output

⏱

Complexity

TimeO(n^2 * m)

SpaceO(n * m)

For each pair of accounts (n^2), we check emails overlap (up to m emails per account). This is very inefficient for large inputs.

💡 For n=1000 accounts with 10 emails each, this means about 1,000,000 comparisons, each checking up to 10 emails, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Union-Find with Email to Account Mapping

💡 This approach uses the union-find data structure to efficiently merge accounts by connecting emails that belong to the same person.

Intuition

Treat each email as a node in a graph. If two emails appear in the same account, union them. Finally, group emails by their root parent to merge accounts.

Algorithm

1. Initialize union-find structure for all emails.
2. Map each email to its owner name.
3. For each account, union all emails in that account.
4. Find root parent for each email and group emails by root.
5. Sort emails in each group and add the owner's name at the front.

💡 The union-find structure efficiently merges sets, but mapping emails to owners and grouping requires careful bookkeeping.

</>

Code

from typing import List

class UnionFind:
    def __init__(self):
        self.parent = {}

    def find(self, x):
        if x != self.parent.setdefault(x, x):
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

def accountsMerge(accounts: List[List[str]]) -> List[List[str]]:
    uf = UnionFind()
    email_to_name = {}

    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            email_to_name[email] = name
            uf.union(first_email, email)

    unions = {}
    for email in email_to_name:
        root = uf.find(email)
        unions.setdefault(root, set()).add(email)

    merged = []
    for root, emails in unions.items():
        merged.append([email_to_name[root]] + sorted(emails))
    return merged

# Driver code
if __name__ == '__main__':
    input_accounts = [["John", "[e-mail]", "[e-mail]"],
                      ["John", "[e-mail]"],
                      ["John", "[e-mail]", "[e-mail]"],
                      ["Mary", "[e-mail]"]]
    print(accountsMerge(input_accounts))

Line Notes

self.parent = {}Initialize parent dictionary for union-find to track email groups

self.parent.setdefault(x, x)Set default parent to itself if email not seen before

uf.union(first_email, email)Union all emails in the same account to connect them

unions.setdefault(root, set()).add(email)Group emails by their root parent to form merged accounts

import java.util.*;

class UnionFind {
    private Map<String, String> parent = new HashMap<>();

    public String find(String x) {
        parent.putIfAbsent(x, x);
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public void union(String x, String y) {
        parent.put(find(x), find(y));
    }
}

public class AccountsMergeUF {
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        UnionFind uf = new UnionFind();
        Map<String, String> emailToName = new HashMap<>();

        for (List<String> account : accounts) {
            String name = account.get(0);
            String firstEmail = account.get(1);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                uf.union(firstEmail, email);
            }
        }

        Map<String, Set<String>> unions = new HashMap<>();
        for (String email : emailToName.keySet()) {
            String root = uf.find(email);
            unions.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
        }

        List<List<String>> merged = new ArrayList<>();
        for (Map.Entry<String, Set<String>> entry : unions.entrySet()) {
            List<String> account = new ArrayList<>();
            account.add(emailToName.get(entry.getKey()));
            account.addAll(entry.getValue());
            merged.add(account);
        }
        return merged;
    }

    public static void main(String[] args) {
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("John", "[e-mail]"),
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("Mary", "[e-mail]")
        );
        System.out.println(accountsMerge(accounts));
    }
}

Line Notes

private Map<String, String> parent = new HashMap<>();Store parent for each email in union-find structure

parent.putIfAbsent(x, x);Initialize parent to itself if email not seen before

uf.union(firstEmail, email);Union emails in the same account to connect them

unions.computeIfAbsent(root, k -> new TreeSet<>()).add(email);Group emails by root and keep them sorted using TreeSet

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

class UnionFind {
    unordered_map<string, string> parent;
public:
    string find(const string& x) {
        if (parent.find(x) == parent.end()) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(const string& x, const string& y) {
        parent[find(x)] = find(y);
    }
};

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    UnionFind uf;
    unordered_map<string, string> emailToName;

    for (auto& account : accounts) {
        string name = account[0];
        string firstEmail = account[1];
        for (int i = 1; i < (int)account.size(); i++) {
            emailToName[account[i]] = name;
            uf.unite(firstEmail, account[i]);
        }
    }

    map<string, set<string>> unions;
    for (auto& [email, name] : emailToName) {
        string root = uf.find(email);
        unions[root].insert(email);
    }

    vector<vector<string>> merged;
    for (auto& [root, emails] : unions) {
        vector<string> account;
        account.push_back(emailToName[root]);
        account.insert(account.end(), emails.begin(), emails.end());
        merged.push_back(account);
    }
    return merged;
}

int main() {
    vector<vector<string>> accounts = {
        {"John", "[e-mail]", "[e-mail]"},
        {"John", "[e-mail]"},
        {"John", "[e-mail]", "[e-mail]"},
        {"Mary", "[e-mail]"}
    };
    vector<vector<string>> result = accountsMerge(accounts);
    for (auto& acc : result) {
        for (auto& s : acc) cout << s << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

unordered_map<string, string> parent;Store parent for each email in union-find structure

if (parent.find(x) == parent.end()) parent[x] = x;Initialize parent to itself if email not seen before

uf.unite(firstEmail, account[i]);Union emails in the same account to connect them

map<string, set<string>> unions;Use map and set to group and sort emails by root parent

class UnionFind {
    constructor() {
        this.parent = new Map();
    }
    find(x) {
        if (!this.parent.has(x)) this.parent.set(x, x);
        if (this.parent.get(x) !== x) {
            this.parent.set(x, this.find(this.parent.get(x)));
        }
        return this.parent.get(x);
    }
    union(x, y) {
        this.parent.set(this.find(x), this.find(y));
    }
}

function accountsMerge(accounts) {
    const uf = new UnionFind();
    const emailToName = new Map();

    for (const account of accounts) {
        const name = account[0];
        const firstEmail = account[1];
        for (const email of account.slice(1)) {
            emailToName.set(email, name);
            uf.union(firstEmail, email);
        }
    }

    const unions = new Map();
    for (const email of emailToName.keys()) {
        const root = uf.find(email);
        if (!unions.has(root)) unions.set(root, new Set());
        unions.get(root).add(email);
    }

    const merged = [];
    for (const [root, emails] of unions.entries()) {
        merged.push([emailToName.get(root), ...Array.from(emails).sort()]);
    }
    return merged;
}

// Driver code
const inputAccounts = [
    ["John", "[e-mail]", "[e-mail]"],
    ["John", "[e-mail]"],
    ["John", "[e-mail]", "[e-mail]"],
    ["Mary", "[e-mail]"]
];
console.log(accountsMerge(inputAccounts));

Line Notes

this.parent = new Map();Initialize parent map for union-find structure

if (!this.parent.has(x)) this.parent.set(x, x);Set default parent to itself if email not seen before

uf.union(firstEmail, email);Union emails in the same account to connect them

unions.get(root).add(email);Group emails by root parent to form merged accounts

⏱

Complexity

TimeO(N * M * α(N*M))

SpaceO(N * M)

N accounts with M emails each. Union-find operations are almost O(1) (α is inverse Ackermann function).

💡 For 1000 accounts with 10 emails each, this is roughly 10,000 union/find operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and scalable, suitable for large inputs and commonly expected in interviews.

🧠

Union-Find with Path Compression and Optimized Grouping

💡 This approach improves the previous union-find by using path compression and sorting emails only once, optimizing runtime and memory usage.

Intuition

Use union-find with path compression to flatten trees, then group emails by root. Sorting is done once per group for output.

Algorithm

1. Initialize union-find with path compression.
2. Map emails to names and union emails in the same account.
3. Find root parent for each email and group emails by root.
4. Sort each group of emails once.
5. Return merged accounts with name and sorted emails.

💡 Path compression drastically reduces find operation time, making union-find near constant time.

</>

Code

from typing import List

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        if x != self.parent.setdefault(x, x):
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            rankX = self.rank.setdefault(rootX, 0)
            rankY = self.rank.setdefault(rootY, 0)
            if rankX < rankY:
                self.parent[rootX] = rootY
            elif rankX > rankY:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def accountsMerge(accounts: List[List[str]]) -> List[List[str]]:
    uf = UnionFind()
    email_to_name = {}

    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            email_to_name[email] = name
            uf.union(first_email, email)

    unions = {}
    for email in email_to_name:
        root = uf.find(email)
        unions.setdefault(root, []).append(email)

    merged = []
    for root, emails in unions.items():
        merged.append([email_to_name[root]] + sorted(emails))
    return merged

# Driver code
if __name__ == '__main__':
    input_accounts = [["John", "[e-mail]", "[e-mail]"],
                      ["John", "[e-mail]"],
                      ["John", "[e-mail]", "[e-mail]"],
                      ["Mary", "[e-mail]"]]
    print(accountsMerge(input_accounts))

Line Notes

self.rank = {}Track tree depth to optimize union by rank and keep trees shallow

rankX = self.rank.setdefault(rootX, 0)Get rank or initialize to zero for rootX

if rankX < rankY:Attach smaller tree under larger to keep tree shallow and optimize find

unions.setdefault(root, []).append(email)Group emails by root parent efficiently for merging

import java.util.*;

class UnionFind {
    private Map<String, String> parent = new HashMap<>();
    private Map<String, Integer> rank = new HashMap<>();

    public String find(String x) {
        parent.putIfAbsent(x, x);
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public void union(String x, String y) {
        String rootX = find(x);
        String rootY = find(y);
        if (!rootX.equals(rootY)) {
            int rankX = rank.getOrDefault(rootX, 0);
            int rankY = rank.getOrDefault(rootY, 0);
            if (rankX < rankY) {
                parent.put(rootX, rootY);
            } else if (rankX > rankY) {
                parent.put(rootY, rootX);
            } else {
                parent.put(rootY, rootX);
                rank.put(rootX, rankX + 1);
            }
        }
    }
}

public class AccountsMergeUFOptimized {
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        UnionFind uf = new UnionFind();
        Map<String, String> emailToName = new HashMap<>();

        for (List<String> account : accounts) {
            String name = account.get(0);
            String firstEmail = account.get(1);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                uf.union(firstEmail, email);
            }
        }

        Map<String, List<String>> unions = new HashMap<>();
        for (String email : emailToName.keySet()) {
            String root = uf.find(email);
            unions.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }

        List<List<String>> merged = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : unions.entrySet()) {
            List<String> account = entry.getValue();
            Collections.sort(account);
            account.add(0, emailToName.get(entry.getKey()));
            merged.add(account);
        }
        return merged;
    }

    public static void main(String[] args) {
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("John", "[e-mail]"),
            Arrays.asList("John", "[e-mail]", "[e-mail]"),
            Arrays.asList("Mary", "[e-mail]")
        );
        System.out.println(accountsMerge(accounts));
    }
}

Line Notes

private Map<String, Integer> rank = new HashMap<>();Store rank to optimize union operations and keep trees balanced

if (!rootX.equals(rootY)) {Only union if roots differ to avoid cycles and redundant unions

unions.computeIfAbsent(root, k -> new ArrayList<>()).add(email);Group emails by root efficiently for merging

Collections.sort(account);Sort emails before adding name at front for consistent output

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

class UnionFind {
    unordered_map<string, string> parent;
    unordered_map<string, int> rank;
public:
    string find(const string& x) {
        if (parent.find(x) == parent.end()) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(const string& x, const string& y) {
        string rootX = find(x);
        string rootY = find(y);
        if (rootX != rootY) {
            int rankX = rank[rootX];
            int rankY = rank[rootY];
            if (rankX < rankY) {
                parent[rootX] = rootY;
            } else if (rankX > rankY) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    UnionFind uf;
    unordered_map<string, string> emailToName;

    for (auto& account : accounts) {
        string name = account[0];
        string firstEmail = account[1];
        for (int i = 1; i < (int)account.size(); i++) {
            emailToName[account[i]] = name;
            uf.unite(firstEmail, account[i]);
        }
    }

    map<string, vector<string>> unions;
    for (auto& [email, name] : emailToName) {
        string root = uf.find(email);
        unions[root].push_back(email);
    }

    vector<vector<string>> merged;
    for (auto& [root, emails] : unions) {
        sort(emails.begin(), emails.end());
        emails.insert(emails.begin(), emailToName[root]);
        merged.push_back(emails);
    }
    return merged;
}

int main() {
    vector<vector<string>> accounts = {
        {"John", "[e-mail]", "[e-mail]"},
        {"John", "[e-mail]"},
        {"John", "[e-mail]", "[e-mail]"},
        {"Mary", "[e-mail]"}
    };
    vector<vector<string>> result = accountsMerge(accounts);
    for (auto& acc : result) {
        for (auto& s : acc) cout << s << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

unordered_map<string, int> rank;Track rank to optimize union and keep trees balanced

if (rootX != rootY) {Only union different sets to avoid cycles and redundant unions

map<string, vector<string>> unions;Use map to group emails by root and keep sorted order

sort(emails.begin(), emails.end());Sort emails before adding name for consistent output

class UnionFind {
    constructor() {
        this.parent = new Map();
        this.rank = new Map();
    }
    find(x) {
        if (!this.parent.has(x)) this.parent.set(x, x);
        if (this.parent.get(x) !== x) {
            this.parent.set(x, this.find(this.parent.get(x)));
        }
        return this.parent.get(x);
    }
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            let rankX = this.rank.get(rootX) || 0;
            let rankY = this.rank.get(rootY) || 0;
            if (rankX < rankY) {
                this.parent.set(rootX, rootY);
            } else if (rankX > rankY) {
                this.parent.set(rootY, rootX);
            } else {
                this.parent.set(rootY, rootX);
                this.rank.set(rootX, rankX + 1);
            }
        }
    }
}

function accountsMerge(accounts) {
    const uf = new UnionFind();
    const emailToName = new Map();

    for (const account of accounts) {
        const name = account[0];
        const firstEmail = account[1];
        for (const email of account.slice(1)) {
            emailToName.set(email, name);
            uf.union(firstEmail, email);
        }
    }

    const unions = new Map();
    for (const email of emailToName.keys()) {
        const root = uf.find(email);
        if (!unions.has(root)) unions.set(root, []);
        unions.get(root).push(email);
    }

    const merged = [];
    for (const [root, emails] of unions.entries()) {
        emails.sort();
        emails.unshift(emailToName.get(root));
        merged.push(emails);
    }
    return merged;
}

// Driver code
const inputAccounts = [
    ["John", "[e-mail]", "[e-mail]"],
    ["John", "[e-mail]"],
    ["John", "[e-mail]", "[e-mail]"],
    ["Mary", "[e-mail]"]
];
console.log(accountsMerge(inputAccounts));

Line Notes

this.rank = new Map();Store rank to optimize union and keep trees balanced

if (rootX !== rootY) {Only union different sets to avoid cycles and redundant unions

unions.get(root).push(email);Group emails by root parent for merging

emails.sort();Sort emails before adding name for consistent output

⏱

Complexity

TimeO(N * M * α(N*M))

SpaceO(N * M)

Path compression and union by rank optimize union-find to near constant time per operation.

💡 This approach is the most efficient and practical for large datasets, making it ideal for interviews.

Interview Verdict: Accepted

This is the optimal union-find solution expected in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimized union-find with path compression in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * m)	O(n * m)	No	Yes	Mention only - never code
2. Union-Find Basic	O(N * M * α(N*M))	O(N * M)	No	Yes	Code if asked for efficient solution
3. Union-Find Optimized with Path Compression	O(N * M * α(N*M))	O(N * M)	No	Yes	Preferred solution to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare for common interview questions and follow-ups.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce union-find and explain how it models the problem.Step 4: Code the union-find solution with path compression.Step 5: Test with examples and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 3min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of union-find, ability to map problem to graph components, and code correctness and efficiency.

Common Follow-ups

• How to handle very large inputs efficiently → use union-find with path compression
• What if accounts have different names but shared emails → merge by emails, name from first occurrence
• How to output merged accounts sorted by name → sort final result by name
• Can you do this without union-find → yes, DFS or BFS on email graph

💡 These follow-ups test deeper understanding of the problem, edge cases, and alternative solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves merging groups with shared elements; 2) Need to find connected components; 3) Efficient union and find operations needed; 4) Output grouped and sorted merged data.

Signature Phrases

accounts with common emailsmerge accountsgroup emails by owner

NOT This Pattern When

Problems that require dynamic programming or greedy approaches without grouping or connectivity.

Similar Problems

Number of Connected Components in an Undirected Graph - similar graph connectivityFriend Circles - grouping friends using union-findGraph Valid Tree - union-find to detect cycles and connectivity

Practice

1. You are given n computers and a list of connections where each connection connects two computers. You want to connect all computers with the minimum number of operations, where each operation can rewire an existing connection. Which algorithmic approach guarantees the optimal solution to determine the minimum operations needed or if it's impossible?

easy

A. Dynamic Programming to find the minimum spanning tree cost

B. Greedy approach that connects the most connected computers first

C. Union-Find (Disjoint Set Union) to count connected components and check redundant connections

D. Depth-First Search to find the longest path and rewire connections accordingly

Solution

1. Step 1: Understand problem requirements

   The problem requires connecting all computers with minimum operations by rewiring existing connections. This involves grouping nodes into connected components and counting redundant edges.

2. Step 2: Identify suitable algorithm

   Union-Find efficiently tracks connected components and redundant edges, enabling quick checks if the network can be connected and how many operations are needed.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-Find is the standard approach for connectivity and component counting [OK]

Hint: Union-Find tracks components and redundant edges efficiently [OK]

Common Mistakes:

• Thinking greedy or DFS alone can guarantee minimal rewiring
• Confusing MST with this problem
• Assuming DP applies directly

2. Examine the following buggy DFS code for counting provinces. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line 4: visited[city] = True

B. Line 2: for neighbor in graph[city]:

C. Line 1: def dfs(city: int):

D. Line 3: if not visited[neighbor]:

Solution

1. Step 1: Understand DFS visit marking

   Visited nodes must be marked before recursive calls to avoid revisiting and infinite loops.

2. Step 2: Identify bug in visit marking

   Marking visited after recursion causes repeated visits and possible infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited marking must be before recursion to prevent cycles [OK]

Hint: Visited marking after recursion causes infinite loops [OK]

Common Mistakes:

• Marking visited too late
• Confusing visited marking with neighbor iteration

3. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order

4. Suppose the problem is extended so that the input matrix isConnected can be updated dynamically with new connections added over time. Which data structure or approach is best suited to efficiently maintain and query the number of provinces after each update?

hard

A. Re-run DFS from scratch after each update to count provinces

B. Use Union-Find (Disjoint Set Union) with path compression to merge sets

C. Maintain adjacency list and run BFS only on updated nodes

D. Use a priority queue to track connected components sizes

Solution

1. Step 1: Understand dynamic updates require efficient merges

   Recomputing connected components from scratch is costly for each update.

2. Step 2: Identify data structure supporting fast union and find

   Union-Find with path compression supports near O(1) merges and queries, ideal for dynamic connectivity.

3. Step 3: Evaluate other options

   BFS or DFS on updates is expensive; priority queue does not maintain connectivity efficiently.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Union-Find is standard for dynamic connectivity problems [OK]

Hint: Dynamic connectivity -> Union-Find with path compression [OK]

Common Mistakes:

• Re-running DFS each update
• Trying BFS on partial graph

5. Suppose the problem is modified so that each pair can be used multiple times but swaps are only allowed between indices connected by a path of pairs (transitive closure). Which modification to the algorithm is necessary to handle this variant efficiently?

hard

A. Use a brute force DFS to try all swap sequences since union-find no longer applies

B. Use BFS to find shortest swap sequences between indices before swapping

C. Sort the entire string once since any character can be swapped anywhere

D. Use union-find to find connected components, then use a priority queue per component to assign characters on-the-fly

Solution

1. Step 1: Understand transitive closure of pairs

   Indices connected by any path form connected components; union-find efficiently finds these.

2. Step 2: Use priority queues per component

   Priority queues allow on-the-fly assignment of smallest available characters to indices in each component.

3. Step 3: Avoid brute force or BFS over sequences

   Brute force or BFS over swap sequences is inefficient; union-find + priority queue is optimal.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Union-find + priority queue handles multiple swaps and transitive connections efficiently [OK]

Hint: Union-find + priority queue handles transitive swaps efficiently [OK]

Common Mistakes:

• Trying brute force DFS
• Sorting entire string ignoring connectivity
• Using BFS for swap sequences