Accounts Merge

1package pkg5leetcode.interview150;2 3/** LC 721 Accounts Merge */4import java.util.*;5 6public class interview150_LC721AccountsMerge {7  static int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }8 9  static List<List<String>> accountsMerge(List<List<String>> accounts) {10    Map<String,Integer> id = new HashMap<>();11    Map<String,String> name = new HashMap<>();12    int n = 0;13    for (List<String> acc : accounts) {14      for (int i = 1; i < acc.size(); i++) {15        id.putIfAbsent(acc.get(i), n++);16        name.putIfAbsent(acc.get(i), acc.get(0));17      }18    }19    int[] p = new int[n]; for (int i = 0; i < n; i++) p[i] = i;20    for (List<String> acc : accounts) {21      int first = id.get(acc.get(1));22      for (int i = 2; i < acc.size(); i++) { int j = id.get(acc.get(i)); p[find(p, first)] = find(p, j); }23    }24    Map<Integer, TreeSet<String>> groups = new HashMap<>();25    for (var e : id.entrySet()) groups.computeIfAbsent(find(p, e.getValue()), k -> new TreeSet<>()).add(e.getKey());26    List<List<String>> res = new ArrayList<>();27    for (var g : groups.values()) {28      List<String> row = new ArrayList<>(g);29      row.add(0, name.get(row.get(0)));30      res.add(row);31    }32    return res;33  }34 35  public static void main(String[] args) {36    System.out.println(accountsMerge(List.of(37      List.of("John","[email protected]","[email protected]"),38      List.of("John","[email protected]","[email protected]"),39      List.of("Mary","[email protected]"))));40  }41}