721. Accounts Merge

/**
 * Using union-find with rank and path compression.
 *
 * Reading and adding the email to Disjoint Set using union = N operations
 * Saving all emails in a set to one parent = N Operations. Thus Total 2N
 * operations using Union-Find. To sort and add name to each list is O(N logN)
 *
 * Thus Total Time Complexity : O(N log N)
 *
 * Space Complexity : O(N)
 *
 * N = Total number of email addresses in the input.
 */
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> result = new ArrayList();
        if (accounts == null || accounts.size() == 0) {
            return result;
        }
        if (accounts.size() == 1) {
            return accounts;
        }

        Map<String, Node> emailToNode = new HashMap();
        Map<String, String> emailToName = new HashMap();

        // Reading all emails from the input List and adding them to Disjoint Set using
        // union.
        for (List<String> acc : accounts) {
            if (acc.size() <= 1) {
                continue;
            }
            String name = acc.get(0);
            String email1 = acc.get(1);
            for (int i = 1; i < acc.size(); i++) {
                String email = acc.get(i);
                emailToName.put(email, name);
                if (!emailToNode.containsKey(email)) {
                    emailToNode.put(email, new Node());
                }
                union(emailToNode.get(email1), emailToNode.get(email));
            }
        }

        Map<Node, TreeSet<String>> userGroups = new HashMap();

        // Saving all emails in a set to one parent in a hashmap.
        for (String email : emailToNode.keySet()) {
            Node parent = findSet(emailToNode.get(email));
            if (!userGroups.containsKey(parent)) {
                userGroups.put(parent, new TreeSet<String>());
            }
            userGroups.get(parent).add(email);
        }

        // Adding the name of the user.
        for (TreeSet<String> userG : userGroups.values()) {
            LinkedList<String> tempList = new LinkedList<>(userG);
            tempList.addFirst(emailToName.get(tempList.get(0)));
            result.add(tempList);
        }

        return result;
    }

    private class Node {
        int rank;
        Node parent;

        Node() {
            rank = 0;
            parent = this;
        }
    }

    private Node findSet(Node node) {
        if (node != node.parent) {
            node.parent = findSet(node.parent);
        }
        return node.parent;
    }

    private void union(Node n1, Node n2) {
        Node p1 = findSet(n1);
        Node p2 = findSet(n2);

        if (p1 == p2) {
            return;
        }

        if (p1.rank >= p2.rank) {
            p1.rank = p1.rank == p2.rank ? p1.rank + 1 : p1.rank;
            p2.parent = p1;
        } else {
            p1.parent = p2;
        }
    }
}