Problem Statement

Given a list accounts where each element accounts[i] is a list of strings, the first element accounts[i][0] is a name, and the remaining elements are email addresses belonging to that account.

The goal is to merge accounts. Two accounts belong to the same person if they share atleast one email address. Note that accounts with the same name may belong to different individuals. After merging, each resulting account must be formatted as a list where the first element is the name, followed by the associated email addresses sorted in ASCII order. The accounts themselves can be returned in any order.

Solution Approach

The core challenge is identifying which accounts belong to the same person based on shared email addresses. A Disjoint Set Union (DSU) data structure is well-suited for this. Each account is assigned a unique identifier. As we iterate through the emails, we maintain a mapping from each email to the first account ID that contained it. If an email is encountered again in a different account, we merge the two account IDs using DSU, indicating they are the same person.

After processing all accounts, we group emails by the root ID of each account (found via DSU). Finally, for each group, we output the name (from any account with that root ID) and the sorted, unique list of emails.

Complexity Analysis

• Time Complexity: O(N log N), where N is the total number of email addresses across all accounts, primarily due to sorting.
• Space Complexity: O(N) for storing the email mappings and DSU structures.

Code Implementation

Python 3

class DisjointSet:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        num_accounts = len(accounts)
        dsu = DisjointSet(num_accounts)
        email_to_id = {}

        for idx, acc in enumerate(accounts):
            for email in acc[1:]:
                if email in email_to_id:
                    dsu.union(email_to_id[email], idx)
                else:
                    email_to_id[email] = idx

        merged_emails = defaultdict(set)
        for idx, acc in enumerate(accounts):
            root = dsu.find(idx)
            for email in acc[1:]:
                merged_emails[root].add(email)

        result = []
        for root_id, emails in merged_emails.items():
            entry = [accounts[root_id][0]] + sorted(emails)
            result.append(entry)
        return result

C++

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }
};

class Solution {
public:
    vector<vector>> accountsMerge(vector<vector>>& accounts) {
        int n = accounts.size();
        DSU dsu(n);
        unordered_map<string int=""> emailMap;

        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < accounts[i].size(); ++j) {
                const string& email = accounts[i][j];
                if (emailMap.count(email)) {
                    dsu.unite(emailMap[email], i);
                } else {
                    emailMap[email] = i;
                }
            }
        }

        unordered_map<int unordered_set="">> groups;
        for (int i = 0; i < n; ++i) {
            int root = dsu.find(i);
            for (int j = 1; j < accounts[i].size(); ++j) {
                groups[root].insert(accounts[i][j]);
            }
        }

        vector<vector>> result;
        for (auto& [rootId, emailSet] : groups) {
            vector<string> entry = {accounts[rootId][0]};
            entry.insert(entry.end(), emailSet.begin(), emailSet.end());
            sort(entry.begin() + 1, entry.end());
            result.push_back(entry);
        }
        return result;
    }
};</string></vector></int></string></vector></vector></int>

C#

public class DisjointSet {
    private int[] parent;
    private int[] rank;

    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

public class Solution {
    public IList<ilist>> AccountsMerge(IList<ilist>> accounts) {
        int count = accounts.Count;
        DisjointSet dsu = new DisjointSet(count);
        Dictionary<string int=""> emailDict = new Dictionary<string int="">();

        for (int i = 0; i < count; i++) {
            for (int j = 1; j < accounts[i].Count; j++) {
                string email = accounts[i][j];
                if (emailDict.ContainsKey(email)) {
                    dsu.Union(emailDict[email], i);
                } else {
                    emailDict[email] = i;
                }
            }
        }

        Dictionary<int hashset="">> mergedGroups = new Dictionary<int hashset="">>();
        for (int i = 0; i < count; i++) {
            int root = dsu.Find(i);
            if (!mergedGroups.ContainsKey(root)) {
                mergedGroups[root] = new HashSet<string>();
            }
            for (int j = 1; j < accounts[i].Count; j++) {
                mergedGroups[root].Add(accounts[i][j]);
            }
        }

        IList<ilist>> result = new List<ilist>>();
        foreach (var kvp in mergedGroups) {
            List<string> entry = new List<string> { accounts[kvp.Key][0] };
            entry.AddRange(kvp.Value.OrderBy(e => e, StringComparer.Ordinal));
            result.Add(entry);
        }
        return result;
    }
}</string></string></ilist></ilist></string></int></int></string></string></ilist></ilist>