Skip to content

721. Accounts Merge 👍

  • Time: $O(nk\log nk + nk\alpha(n)) = O(nk\log nk)$, where $k = \max(|\texttt{accounts[i]}|)$
  • Space: $O(n + nk) = O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class UnionFind {
 public:
  UnionFind(int n) : id(n), sz(n, 1) {
    iota(id.begin(), id.end(), 0);
  }

  void unionBySize(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (sz[i] < sz[j]) {
      sz[j] += sz[i];
      id[i] = j;
    } else {
      sz[i] += sz[j];
      id[j] = i;
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
  vector<int> sz;
};

class Solution {
 public:
  vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    vector<vector<string>> ans;
    unordered_map<string, int> emailToIndex;        // {email: index}
    unordered_map<int, set<string>> indexToEmails;  // {index: {emails}}
    UnionFind uf(accounts.size());

    for (int i = 0; i < accounts.size(); ++i) {
      const string name = accounts[i][0];
      for (int j = 1; j < accounts[i].size(); ++j) {
        const string email = accounts[i][j];
        const auto it = emailToIndex.find(email);
        if (it == emailToIndex.end()) {
          emailToIndex[email] = i;
        } else {
          uf.unionBySize(i, it->second);
        }
      }
    }

    for (const auto& [email, index] : emailToIndex)
      indexToEmails[uf.find(index)].insert(email);

    for (const auto& [index, emails] : indexToEmails) {
      const string name = accounts[index][0];
      vector<string> row{name};
      row.insert(row.end(), emails.begin(), emails.end());
      ans.push_back(row);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class UnionFind {
  public UnionFind(List<List<String>> accounts) {
    for (List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i) {
        final String email = account.get(i);
        id.putIfAbsent(email, email);
      }
  }

  public void union(final String u, final String v) {
    id.put(find(u), find(v));
  }

  public String find(final String u) {
    if (u != id.get(u))
      id.put(u, find(id.get(u)));
    return id.get(u);
  }

  private Map<String, String> id = new HashMap<>();
}

class Solution {
  public List<List<String>> accountsMerge(List<List<String>> accounts) {
    List<List<String>> ans = new ArrayList<>();
    Map<String, String> emailToName = new HashMap<>();
    Map<String, TreeSet<String>> idEmailToEmails = new HashMap<>();
    UnionFind uf = new UnionFind(accounts);

    for (final List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i)
        emailToName.putIfAbsent(account.get(i), account.get(0));

    for (final List<String> account : accounts)
      for (int i = 2; i < account.size(); ++i)
        uf.union(account.get(i), account.get(i - 1));

    for (final List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i) {
        final String id = uf.find(account.get(i));
        idEmailToEmails.putIfAbsent(id, new TreeSet<>());
        idEmailToEmails.get(id).add(account.get(i));
      }

    for (final String idEmail : idEmailToEmails.keySet()) {
      List<String> emails = new ArrayList<>(idEmailToEmails.get(idEmail));
      final String name = emailToName.get(idEmail);
      emails.add(0, name);
      ans.add(emails);
    }

    return ans;
  }
}