Accounts Merge

Problem Statement

The task is to merge multiple user accounts into unique ones based on common email addresses found among them. We are provided with a list named accounts, where each sublist represents an individual's account that includes the person's name followed by their email addresses. It is important to note that the existence of one or more shared email addresses across these sublists is the indicator that they belong to the same individual.

A critical detail in the merging process is that, even if two accounts share a name, they will be considered separate unless a common email address is found. This is accounted for since people may share names but have different accounts. Once accounts are identified for merging, the consolidated account should have emails sorted in lexicographical order, and each account should continue to start with the user's name. The final output is not required to maintain any specific order for the accounts.

Examples

Example 1

Input:

accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Output:

[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Explanation:

The first and second John's are the same person as they have the common email "johnsmith@mail.com".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'],
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2

Input:

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"]]

Output:

[["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) is a valid email.

Approach and Intuition

Given the problem requires the merging of accounts based on commonalities in email addresses among potentially fragmented account information, it is analogous to identifying connected components in a graph:

1. Modeling the Accounts as a Graph:

   • Think of each unique email as a node.
   • Each user can be considered a connection (or an edge) that ties these email nodes together, based on which emails are listed under their name. If two accounts have overlapping emails, they share edges, forming connected components in a graph.

2. Utilize Union-Find Data Structure:

   • This is apt for dynamically merging sets and finding connected components.
   • At each step, union operations can help merge accounts that share a common email (node).

3. Mapping and Compaction:

   • From the graph perspective, harvest all nodes (emails) connected to each other and map them back to users.
   • For every component (unique user discovered through the connected component analysis), compile and sort the emails.

4. Reconstruction of the Final Account List:

   • Post mapping and sorting, reconstruct the accounts in the required format starting with the user's name followed by their sorted list of emails.
   • The sequence of accounts in the output doesn’t matter, providing flexibility in how the list is constructed.

This approach effectively aggregates scattered account information into organized, consolidated account records using graph theory concepts combined with efficient data structures for set management.

Solutions

class DisjointSetUnion {
public:
    vector<int> leader;
    vector<int> rank;
        
    DisjointSetUnion(int size) : leader(size), rank(size) {
        for (int i = 0; i < size; ++i) {
            leader[i] = i;
            rank[i] = 1;
        }
    }
        
    int find(int x) {
        if (x == leader[x]) {
            return x;
        }
        return leader[x] = find(leader[x]);
    }
        
    void unionByRank(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
            
        if (rootX == rootY) return;
            
        if (rank[rootX] >= rank[rootY]) {
            rank[rootX] += rank[rootY];
            leader[rootY] = rootX;
        } else {
            rank[rootY] += rank[rootX];
            leader[rootX] = rootY;
        }
    }
};
    
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        DisjointSetUnion dsu(n);
            
        unordered_map<string, int> emailToIndex;
            
        for (int i = 0; i < n; i++) {
            int accountLen = accounts[i].size();
    
            for (int j = 1; j < accountLen; j++) {
                string email = accounts[i][j];
                    
                if (emailToIndex.find(email) == emailToIndex.end()) {
                    emailToIndex[email] = i;
                } else {
                    dsu.unionByRank(i, emailToIndex[email]);
                }
            }
        }
            
        unordered_map<int, vector<string>> groupedEmails;
        for (const auto& pair : emailToIndex) {
            int root = dsu.find(pair.second);
            groupedEmails[root].push_back(pair.first);
        }
    
        vector<vector<string>> mergedAccounts;
        for (auto& emails : groupedEmails) {
            int root = emails.first;
            vector<string> mergedAccount = {accounts[root][0]};
            mergedAccount.insert(end(mergedAccount), begin(emails.second), end(emails.second));
            sort(next(begin(mergedAccount)), end(mergedAccount));
            mergedAccounts.push_back(mergedAccount);
        }
            
        return mergedAccounts;
    }
};