Meta — Accounts Merge (Union-Find on Emails)

Problem (Meta Graphs Classic)

Given a list of accounts [name, email1, email2, ...], merge accounts that share any email. Return sorted merged accounts.

Example:

[["John","j@a","j@b"],["John","j@b","j@c"],["Mary","m@a"]]
→ [["John","j@a","j@b","j@c"],["Mary","m@a"]]

Key Insight — Union-Find on Emails

Each email → node in Union-Find
For each account, union all emails together
Group emails by root → sort → prepend name

Solutions

Python

from collections import defaultdict

def accountsMerge(accounts):
    parent = {}
    email_to_name = {}

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

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

    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name
            union(acc[1], email)

    groups = defaultdict(list)
    for email in parent:
        groups[find(email)].append(email)

    return [[email_to_name[root]] + sorted(emails) for root, emails in groups.items()]

JavaScript

function accountsMerge(accounts) {
    const parent={}, nameMap={};
    const find=x=>parent[x]===x?x:parent[x]=find(parent[x]);
    const union=(x,y)=>parent[find(x)]=find(y);
    for(const acc of accounts){
        const name=acc[0];
        for(let i=1;i<acc.length;i++){if(!parent[acc[i]])parent[acc[i]]=acc[i];nameMap[acc[i]]=name;if(i>1)union(acc[1],acc[i]);}
    }
    const groups=new Map();
    for(const e of Object.keys(parent)){const r=find(e);if(!groups.has(r))groups.set(r,[]);groups.get(r).push(e);}
    return [...groups.values()].map(emails=>([nameMap[find(emails[0])],...emails.sort()]));
}

Java

import java.util.*;
public List<List<String>> accountsMerge(List<List<String>> accs) {
    Map<String,String> par=new HashMap<>(), names=new HashMap<>();
    for(List<String> acc:accs){String name=acc.get(0);for(int i=1;i<acc.size();i++){par.putIfAbsent(acc.get(i),acc.get(i));names.put(acc.get(i),name);if(i>1)union(par,acc.get(1),acc.get(i));}}
    Map<String,List<String>> groups=new HashMap<>();
    for(String e:par.keySet()) groups.computeIfAbsent(find(par,e),k->new ArrayList<>()).add(e);
    List<List<String>> res=new ArrayList<>();
    for(Map.Entry<String,List<String>> g:groups.entrySet()){Collections.sort(g.getValue());List<String> r=new ArrayList<>();r.add(names.get(g.getKey()));r.addAll(g.getValue());res.add(r);}
    return res;
}
String find(Map<String,String> p,String x){if(!p.get(x).equals(x))p.put(x,find(p,p.get(x)));return p.get(x);}
void union(Map<String,String> p,String x,String y){p.put(find(p,x),find(p,y));}

C++

#include <unordered_map>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
unordered_map<string,string> par; unordered_map<string,string> names;
string find(string x){return par[x]==x?x:par[x]=find(par[x]);}
void unite(string x,string y){par[find(x)]=find(y);}
vector<vector<string>> accountsMerge(vector<vector<string>>& accs) {
    for(auto& a:accs){string nm=a[0];for(int i=1;i<(int)a.size();i++){if(!par.count(a[i]))par[a[i]]=a[i];names[a[i]]=nm;if(i>1)unite(a[1],a[i]);}}
    map<string,vector<string>> groups;
    for(auto& [e,_]:par) groups[find(e)].push_back(e);
    vector<vector<string>> res;
    for(auto& [root,emails]:groups){sort(emails.begin(),emails.end());vector<string> r={names[root]};r.insert(r.end(),emails.begin(),emails.end());res.push_back(r);}
    return res;
}

C

/* C: string-keyed union-find using hash map + sorted merge */