@@ -0,0 +1,2713 @@
+// Problem is boils down to solving connected components for all of the emails (vertices) in the%0A// graph. I think the code can be simplified by not using Node class, but that makes it a bit%0A// easier to read.%0A//%0A// Time complexity: max(O(AE), O(ElogE)); it depends on number of unique emails per account.%0A// Space complexity: O(E)%0A// E - number of emails, A - number of accounts%0A%0Aclass Solution %7B%0A  static class Node %7B%0A    String email; // non-null%0A    String name; // non-null%0A%0A    Node(String email, String name) %7B%0A      this.email = email;%0A      this.name = name;%0A    %7D%0A%0A    @Override%0A    public int hashCode() %7B%0A      return email.hashCode();%0A    %7D%0A%0A    @Override%0A    public boolean equals(Object obj) %7B%0A      if (obj instanceof Node) return ((Node) obj).email.equals(email);%0A      return false;%0A    %7D%0A  %7D%0A%0A  public List%3CList%3CString%3E%3E accountsMerge(List%3CList%3CString%3E%3E accounts) %7B%0A    List%3CList%3CString%3E%3E res = new ArrayList%3CList%3CString%3E%3E();%0A    HashSet%3CNode%3E visited = new HashSet%3CNode%3E();%0A    HashMap%3CNode, List%3CNode%3E%3E graph = new HashMap%3CNode, List%3CNode%3E%3E();%0A%0A    for (List%3CString%3E account : accounts) %7B%0A      if (account.size() %3E 1) %7B%0A        String name = account.get(0);%0A        Node prev = new Node(account.get(1), name);%0A        if (!graph.containsKey(prev)) %7B%0A          graph.put(prev, new ArrayList%3CNode%3E());%0A        %7D%0A        for (int i = 2; i %3C account.size(); i++) %7B%0A          Node curr = new Node(account.get(i), name);%0A          if (!graph.containsKey(curr)) %7B%0A            graph.put(curr, new ArrayList%3CNode%3E());%0A          %7D%0A          graph.get(prev).add(curr);%0A          graph.get(curr).add(prev);%0A          prev = curr;%0A        %7D%0A      %7D else %7B%0A        res.add(account);%0A      %7D%0A    %7D%0A%0A    for (Node n : graph.keySet()) %7B%0A      if (!visited.contains(n)) %7B%0A        List%3CNode%3E cmp = new ArrayList%3CNode%3E();%0A        component(n, graph, visited, cmp);%0A        res.add(convert(cmp));%0A      %7D%0A    %7D%0A%0A    return res;%0A  %7D%0A%0A  // Finds a component%0A  private void component(%0A      Node start, HashMap%3CNode, List%3CNode%3E%3E graph, HashSet%3CNode%3E visited, List%3CNode%3E res) %7B%0A    if (visited.contains(start)) return;%0A    visited.add(start);%0A    res.add(start);%0A    for (Node child : graph.get(start)) %7B%0A      component(child, graph, visited, res);%0A    %7D%0A  %7D%0A%0A  // Converts nodes into the answer + sorting%0A  private List%3CString%3E convert(List%3CNode%3E nodes) %7B%0A    List%3CString%3E res = new ArrayList%3CString%3E();%0A    if (nodes.size() %3E 0) %7B%0A      res.add(nodes.get(0).name);%0A      String%5B%5D arr = new String%5Bnodes.size()%5D;%0A      for (int i = 0; i %3C nodes.size(); i++) %7B%0A        arr%5Bi%5D = nodes.get(i).email;%0A      %7D%0A      Arrays.sort(arr);%0A      for (String s : arr) %7B%0A        res.add(s);%0A      %7D%0A    %7D%0A    return res;%0A  %7D%0A%7D%0A

add solution