Accounts Merge

mediumGraphs: Topological Sort & Union-Find144 stepsJava · Python · C++

Merge accounts that share any email. Union every email in an account with the account's first email. Then group emails by their root, sort each group, and attach the owner's name.

▶ Watch the animated trace

Traced input: accounts = [[John, a@x, b@x], [John, c@x], [John, b@x, d@x], [Mary, m@x]] → [["John", "a@x", "b@x", "d@x"], ["John", "c@x"], ["Mary", "m@x"]]. Original problem: neetcode.io/problems/accounts-merge

Complexity

BestO(N log N)

AverageO(N log N)

WorstO(N log N)

SpaceO(N)

N total emails; sorting the groups dominates.

Key idea

Emails are the nodes; being in the same account is an edge.
Union-find with a HashMap<String, String> parent handles string keys.
The same person can have two accounts with the same name that don't share emails; they stay separate.

Common mistakes

Merging by name: different people can share a name.
Forgetting to sort emails within each merged account.

Solution

Java

Map<String, String> par = new HashMap<>();

String findEmail(String x) {
    if (!par.get(x).equals(x)) par.put(x, findEmail(par.get(x)));
    return par.get(x);
}

List<List<String>> accountsMerge(List<List<String>> accounts) {
    par.clear();
    Map<String, String> owner = new HashMap<>();
    for (List<String> acc : accounts) {
        String first = acc.get(1);
        for (int i = 1; i < acc.size(); i++) {
            String email = acc.get(i);
            par.putIfAbsent(email, email);
            owner.put(email, acc.get(0));
            par.put(findEmail(email), findEmail(first));
        }
    }
    Map<String, TreeSet<String>> groups = new HashMap<>();
    for (String email : par.keySet()) groups.computeIfAbsent(findEmail(email), k -> new TreeSet<>()).add(email);
    List<List<String>> res = new ArrayList<>();
    for (TreeSet<String> emails : groups.values()) {
        List<String> acc = new ArrayList<>();
        acc.add(owner.get(emails.first()));
        acc.addAll(emails);
        res.add(acc);
    }
    return res;
}

Python

def accountsMerge(accounts: List[List[str]]) -> List[List[str]]:
    parent, owner = {}, {}

    def find(x: str) -> str:
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]

    for acc in accounts:
        first = acc[1]
        for email in acc[1:]:
            parent.setdefault(email, email)
            owner[email] = acc[0]
            parent[find(email)] = find(first)
    groups = defaultdict(list)
    for email in parent: groups[find(email)].append(email)
    res = [[owner[emails[0]]] + sorted(emails) for emails in groups.values()]
    return sorted(res, key=lambda a: a[1])

C++

unordered_map<string, string> par;

string findEmail(const string& x) {
    if (par[x] != x) par[x] = findEmail(par[x]);
    return par[x];
}

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    par.clear();
    unordered_map<string, string> owner;
    for (auto& acc : accounts) {
        for (size_t i = 1; i < acc.size(); i++) {
            if (!par.count(acc[i])) par[acc[i]] = acc[i];
            owner[acc[i]] = acc[0];
            par[findEmail(acc[i])] = findEmail(acc[1]);
        }
    }
    map<string, set<string>> groups;
    for (auto& [email, p] : par) groups[findEmail(email)].insert(email);
    vector<vector<string>> res;
    for (auto& [root, emails] : groups) {
        vector<string> acc{owner[*emails.begin()]};
        acc.insert(acc.end(), emails.begin(), emails.end());
        res.push_back(acc);
    }
    sort(res.begin(), res.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Same name, different people No shared email, so they stay separate.	`accounts = [[Alex, a@x], [Alex, b@x]]`	`[["Alex", "a@x"], ["Alex", "b@x"]]`
Chain of shared emails Transitive links merge all three.	`accounts = [[K, a, b], [K, b, c], [K, c, d]]`	`[["K", "a", "b", "c", "d"]]`
Duplicate email in one account Each email appears once in the output.	`accounts = [[Z, z, z]]`	`[["Z", "z"]]`