Accounts Merge

medium union find dfs graph

Problem

Given a list of accounts where each entry has a name followed by emails, merge entries that share any email under the same owner. Return the merged accounts with each name followed by its sorted emails.

Input[["John","a@x","b@x"],["John","b@x","c@x"],["Mary","m@x"]]

Output[["John","a@x","b@x","c@x"],["Mary","m@x"]]

The two John accounts share b@x, so they merge into one.

input

def accountsMerge(accounts):
    parent = {}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    owner = {}
    for acc in accounts:
        name = acc[0]
        for e in acc[1:]:
            parent.setdefault(e, e); owner[e] = name
            parent[find(e)] = find(acc[1])
    groups = {}
    for e in parent:
        groups.setdefault(find(e), []).append(e)
    return [[owner[r]] + sorted(es) for r, es in groups.items()]

function accountsMerge(accounts) {
  const parent = new Map(), owner = new Map();
  const find = x => { while (parent.get(x) !== x) { parent.set(x, parent.get(parent.get(x))); x = parent.get(x); } return x; };
  for (const acc of accounts) {
    for (let i = 1; i < acc.length; i++) {
      if (!parent.has(acc[i])) parent.set(acc[i], acc[i]);
      owner.set(acc[i], acc[0]);
      parent.set(find(acc[i]), find(acc[1]));
    }
  }
  const groups = new Map();
  for (const e of parent.keys()) {
    const r = find(e);
    if (!groups.has(r)) groups.set(r, []);
    groups.get(r).push(e);
  }
  return [...groups].map(([r, es]) => [owner.get(r), ...es.sort()]);
}

class Solution {
  Map<String,String> parent = new HashMap<>();
  String find(String x) { while (!parent.get(x).equals(x)) { parent.put(x, parent.get(parent.get(x))); x = parent.get(x); } return x; }
  public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String,String> owner = new HashMap<>();
    for (List<String> a : accounts) for (int i = 1; i < a.size(); i++) {
      parent.putIfAbsent(a.get(i), a.get(i));
      owner.put(a.get(i), a.get(0));
      parent.put(find(a.get(i)), find(a.get(1)));
    }
    Map<String,List<String>> groups = new HashMap<>();
    for (String e : parent.keySet()) groups.computeIfAbsent(find(e), k -> new ArrayList<>()).add(e);
    List<List<String>> res = new ArrayList<>();
    for (var en : groups.entrySet()) { Collections.sort(en.getValue()); en.getValue().add(0, owner.get(en.getKey())); res.add(en.getValue()); }
    return res;
  }
}

class Solution {
public:
  unordered_map<string,string> parent;
  string find(string x){ while(parent[x]!=x){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; }
  vector<vector<string>> accountsMerge(vector<vector<string>>& accounts){
    unordered_map<string,string> owner;
    for (auto& a : accounts) for (int i = 1; i < (int)a.size(); i++){
      if(!parent.count(a[i])) parent[a[i]] = a[i];
      owner[a[i]] = a[0];
      parent[find(a[i])] = find(a[1]);
    }
    unordered_map<string,vector<string>> groups;
    for (auto& [e,_] : parent) groups[find(e)].push_back(e);
    vector<vector<string>> res;
    for (auto& [r, es] : groups){ sort(es.begin(), es.end()); es.insert(es.begin(), owner[r]); res.push_back(es); }
    return res;
  }
};

Explanation

Two accounts belong to the same person if they share even one email. So the real question is: which emails are connected? This is a grouping problem, and union-find (also called disjoint-set) is the perfect tool.

We treat every email as a node. Within one account, all of its emails clearly belong together, so we union each email with the account's first email. We also remember which person owner each email belongs to.

The find function returns the representative "root" of an email's group, and union merges two roots into one. After processing all accounts, every email that is transitively connected ends up with the same root.

Finally we bucket emails by their root, sort each bucket, and stick the owner's name in front. Example: John:a@x,b@x and John:b@x,c@x share b@x, so a@x, b@x, c@x all share a root and merge into one John account, while Mary:m@x stays separate.

Time: O(N alpha(N) log N) Space: O(N)