721. Accounts Merge

📝 Problem Details

• Title: 721. Accounts Merge
• Link: https://leetcode.com/problems/accounts-merge/
• Difficulty: Medium
• Tags/Categories: {{tags/categories}}

input 2D array accounts where accounts[i] is a list of strings accounts[i][0] is a name the following elements in accounts[i] are emails representing emails of the account two accounts are merged if they share at least one common email

💭What Were My Initial Thoughts?

- initially thought this was a basic grouping problem, maybe solvable using a hashmap or sorting
- the main challenge is identifying connected components 
	- accounts that are indirectly linked through shared emails 

🤔What Did I Struggle With?

the problem statement itself is a long and a little confusing 

💡 Explanation of Solution

treat each email as a node in a graph
if two emails appear in the same account, they're apart of the same connected component

- we can use union-find (DSU) to connect emails 
1. for each account, union all emails with the first email in that account
2. keep a map from each email to the account name 
3. use the find operation to group emails by their root representative 
4. collect and sort emails for each root, attach name and return 

⌛ Complexity Analysis

Time Complexity: O(E * α(E))
- Let n be the number of accounts (nodes)
- Let R be the total number of emails (edges)
- Inverse Ackerman Function being almost constant

Space Complexity: O(E) for storing email to name mappings and parent tracking

💻 Implementation of Solution

class DSU {
public:
    unordered_map<string, string> parent;
 
    // Find with path compression
    string find(string x) {
        if (parent.find(x) == parent.end()) {
            parent[x] = x;
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
 
    // Union operation
    void unite(string x, string y) {
        string rootX = find(x);
        string rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
};
 
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        DSU dsu;
        unordered_map<string, string> emailToName;
 
        // Step 1: Connect emails in the same account
        for (const auto& account : accounts) {
            string name = account[0];
            for (int i = 1; i < account.size(); ++i) {
                emailToName[account[i]] = name;
                dsu.find(account[i]); // Ensure email is initialized in DSU
                if (i > 1) {
                    dsu.unite(account[i], account[1]); // Union with first email in the account
                }
            }
        }
 
        // Step 2: Group emails by their root parent
        unordered_map<string, set<string>> rootToEmails;
        for (const auto& [email, _] : emailToName) {
            string root = dsu.find(email);
            rootToEmails[root].insert(email);
        }
 
        // Step 3: Format the result
        vector<vector<string>> result;
        for (const auto& [root, emails] : rootToEmails) {
            vector<string> mergedAccount;
            mergedAccount.push_back(emailToName[root]);
            mergedAccount.insert(mergedAccount.end(), emails.begin(), emails.end());
            result.push_back(mergedAccount);
        }
 
        return result;
    }
};