Accounts Merge

Thought Process

This problem requires merging accounts that share common emails. The key is to use Union-Find (Disjoint Set Union) to efficiently group connected emails. First, we initialize each email as its own parent. Then, we union emails from the same account. After grouping, we collect all emailsunder their root parent and format the results. The path compression in the 'find' operation ensures optimal performance.

class Solution {

    // This find is using path compression
    // With path compression, instead of following the chain every time, 
    // we make each email directly point to the root when we find it. 
    // This way, next time it's an  instant lookup.
    public String find(String email, Map<String,String> parentMap){

        if(!parentMap.get(email).equals(email)){
            // parentMap.put(email,find(parentMap.get(email),parentMap));
            email = find(parentMap.get(email),parentMap);
        }
        return email;
        // return parentMap.get(email);
    }
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        
        Map<String,String> mailToPerson = new HashMap<>();
        Map<String,String> parentMap = new HashMap<>();
        Map<String,TreeSet<String>> parentToEmails = new HashMap<>(); // First email to All of its child

        // Initialization
        for(List<String> entity : accounts){

            for(int i=1;i<entity.size();i++){

                mailToPerson.put(entity.get(i),entity.get(0)); // Email to Name of Person
                parentMap.put(entity.get(i),entity.get(i)); // Every email is parent of itself
            }
        }
        // Assign Parents
        for(List<String> entity : accounts){

            String parentOfFirstEmail = find(entity.get(1),parentMap);
            for(int i=2;i<entity.size();i++){

                String parentOfChildEmail = find(entity.get(i),parentMap);
                parentMap.put(parentOfChildEmail,parentOfFirstEmail);
            }
        }
        // Construct the ans in Mail --> All Child Mails ( including Parent mail)
        for(List<String> entity : accounts){

            String parentOfFirstemail = find(entity.get(1),parentMap);
            for(int i=1;i<entity.size();i++){

                parentToEmails.putIfAbsent(parentOfFirstemail,new TreeSet<>());
                parentToEmails.get(parentOfFirstemail).add(entity.get(i));
            }
        }

        // Store Answer as asked in the question
        List<List<String>> ans = new ArrayList<>();
        for(String entity : parentToEmails.keySet()){

            List<String> list = new ArrayList<>(parentToEmails.get(entity));  // All childs corresponding to first email
            list.add(0,mailToPerson.get(entity)); // Add person name on top index
            ans.add(list);
        }
        return ans;
    }
}

Code Complexity

Time Complexity: O(n α(n))

Where n is the total number of emails and α is the inverse Ackermann function (nearly constant time due to path compression).

Space Complexity: O(n)

We use O(n) space to store parent relationships, email mappings, and the final result.

Java: Accounts Merge

Thought Process

Code Complexity

Time Complexity: O(n α(n))

Space Complexity: O(n)