Problem Description

Given a list of accounts where each account is represented as a list of strings, the first element being a name and the remaining elements being email addresses associated with that account. The task is to merge these accounts based on shared email addresses. If two accounts have at least one email in common, they belong to the same person. Note that accounts with identical names might still belong to different individuals if they don't share any email addresses. After merging, each account should have the name as the first element followed by all unique email addresses sorted in ASCII order. The merged accounts can be returned in any order.

Example 1:

<strong>Input:</strong> accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
<strong>Output:</strong> [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
<strong>Explanation:</strong>
The first and third John accounts belong to the same person because they share "johnsmith@mail.com". The second John and Mary are different individuals as they don't share any email addresses. The output order may vary.

Example 2:

<strong>Input:</strong> accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
<strong>Output:</strong> [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Constraints:

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• 1 <= accounts[i][j].length <= 30
• accounts[i][0] consists of English letters
• accounts[i][j] (for j > 0) are valid email addresses

Solution Approach

The problem requires identifying all email addreses that belong to the same individual and merging their accounts. This can be efficiently solved using the Union-Find (Disjoint Set Union) data structure, which helps in grouping related elmeents.

The approach involves the following steps:

1. Create mappings from email addresses to unique indices and to corresponding names.
2. Initialize a Union-Find structure to manage the connections between email addresses.
3. For each account, union all email addresses within that account since they belong to the same person.
4. Group all email addresses by thier root parent in the Union-Find structure.
5. For each group, sort the email addresses and prepend the corresponding name to form the merged account.

Implementation

class DisjointSet {
private:
    vector<int> parent;
    vector<int> rank;
    
public:
    DisjointSet(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unionElements(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

class Solution {
public:
    vector<vector>> accountsMerge(vector<vector>>& accounts) {
        unordered_map<string int=""> emailToId;
        unordered_map<string string=""> emailToName;
        int id = 0;
        
        // Assign unique IDs to each email and record name associations
        for (const auto& account : accounts) {
            const string& name = account[0];
            for (int i = 1; i < account.size(); i++) {
                const string& email = account[i];
                if (emailToId.find(email) == emailToId.end()) {
                    emailToId[email] = id++;
                    emailToName[email] = name;
                }
            }
        }
        
        // Initialize disjoint set
        DisjointSet ds(id);
        
        // Union emails within the same account
        for (const auto& account : accounts) {
            int firstEmailId = emailToId[account[1]];
            for (int i = 2; i < account.size(); i++) {
                int currentEmailId = emailToId[account[i]];
                ds.unionElements(firstEmailId, currentEmailId);
            }
        }
        
        // Group emails by their root
        unordered_map<int vector="">> idToEmails;
        for (const auto& entry : emailToId) {
            const string& email = entry.first;
            int rootId = ds.find(emailToId[email]);
            idToEmails[rootId].push_back(email);
        }
        
        // Prepare the result
        vector<vector>> result;
        for (auto& entry : idToEmails) {
            vector<string> mergedAccount;
            const vector<string>& emails = entry.second;
            sort(emails.begin(), emails.end());
            
            mergedAccount.push_back(emailToName[emails[0]]);
            for (const string& email : emails) {
                mergedAccount.push_back(email);
            }
            
            result.push_back(mergedAccount);
        }
        
        return result;
    }
};
</string></string></vector></int></string></string></vector></vector></int></int>

Complexity Analysis

Time Complexity: O(n log n), where n is the number of unique email addresses. The Union-Find operations (with path compression and union by rank) take nearly constant time per operation. The dominant factor is sorting the email addresses, which is O(n log n).

Space Complexity: O(n), where n is the number of unique email addresses. The space is used for storing the mappings and the Union-Find data structure.