Accounts Merge - Disjoint Set Union (DSU)

This chapter covers the classic "Accounts Merge" problem (LeetCode 721), a fundamental graph-to-DSU application. The problem asks us to consolidate a collection of email accounts belonging to various individuals where overlapping email addresses imply they belong to the exact same person.

1. Why Do We Need This? (Problem Statement & Status Quo)

We are given a list of accounts where each account consists of a person's name followed by a list of their email addresses. For instance:

Account 0: ["John", "j1@com", "j2@com", "j3@com"]
Account 1: ["John", "j4@com"]
Account 2: ["Raj", "r1@com", "r2@com"]
Account 3: ["John", "j1@com", "j5@com"]
Account 4: ["Raj", "r2@com", "r3@com"]
Account 5: ["Mary", "m1@com"]

The Core Challenge

• Same Name, Different People: Two entries might share the exact same name (e.g., "John") but represent completely different individuals if their email domains/addresses do not intersect.
• Transitive Overlapping: If Account 0 has j1@com and Account 3 also has j1@com, both accounts belong to the same physical person. Any other emails associated with either account must be merged into a single consolidated profile.
• Sorting Requirement: The final merged output must contain the name followed by all unique email addresses sorted in lexicographical (alphabetical) order.

2. Core Mental Model & Analogy

Real-Life Analogy: Shared Contact Book / Membership Lists

Imagine a club where members write down their names and email addresses on sign-up sheets over time.

• Person A fills out sheet #0 with emails [email1, email2].
• Person B fills out sheet #3 later, but accidentally (or intentionally) includes email1 alongside a new email5.
• Because both sheets contain email1, the club administrator realizes sheet #0 and sheet #3 belong to the exact same human being. The administrator merges the sheets, drops the duplicate email1, and keeps email5.

Dynamic Connectivity via DSU

Because merges happen dynamically as we inspect overlapping emails across different account indexes, this is a textbook application for the Disjoint Set Union (DSU) data structure. DSU efficiently manages partitioning elements into disjoint sets and supports two primary operations:

1. findParent(node): Identifies the ultimate representative (boss) of a set.
2. unionBySize(u, v): Merges two sets together based on their sizes.

3. Step-by-Step Evolution of the Approach

Naive Approach vs. DSU Approach

• Naive Approach: Build an explicit graph where every email is a node, and edges connect emails appearing in the same account array. Then run Depth First Search (DFS) or Breadth First Search (BFS) to find connected components. While feasible, building a dense graph of string keys and managing adjacency lists is cumbersome and prone to overhead.
• Better Approach (DSU with Index Mapping): Treat each account index ($0, 1, 2, \dots, N-1$) as a DSU node. Use a hash map (map<string, int>) to track which email address was first seen at which account index. If an email is encountered again at a different account index, we union the current account index with the original account index stored in the map.

4. Step 1: Mapping Emails and Building Components

We initialize our DSU structure with a size equal to the total number of accounts ($N$). Each account index is initially its own parent:

Index:    0    1    2    3    4    5
Parent:   0    1    2    3    4    5

We iterate through every account starting from index 1 (skipping index 0 because it holds the person's name):

DSU State After Processing All Accounts

After evaluating all accounts and performing necessary unions, the disjoint sets link connected account indexes together:

• Account 0 and Account 3 are merged (Root: 0).
• Account 2 and Account 4 are merged (Root: 2).
• Account 1 stands alone (Root: 1).
• Account 5 stands alone (Root: 5).

5. Step 2: Grouping Emails by Ultimate Parent

Once all component connections are established via DSU, we must gather every email address and attach it to its component's ultimate boss (root parent).

We iterate through our email-to-node mapping:

1. For each email, find its associated account node.
2. Query DSU to find the ultimate parent: root = ds.findParent(node).
3. Insert the email into a data structure grouped by this root index (mergedMail[root].push_back(email)).

Even if an email was originally logged under account 3, because account 3's ultimate parent is 0, that email correctly routes to mergedMail[0].

6. Step 3: Sorting and Formatting the Final Output

With all emails correctly grouped under their ultimate root parents, we perform the final transformation:

1. Sort Emails: For each non-empty group in mergedMail, sort the email addresses lexicographically.
2. Prepend Name: Retrieve the person's name from the original input using the root index (details[root][0]).
3. Construct Result: Combine the name and sorted emails into a temporary list and push it to the final answer collection.

7. Complete Implementation Code

Here is the complete production-grade implementation in C++ and Java.

C++ Implementation

#class DisjointSet {
    vector<int> rank, parent, size;
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& details) {
        int n = details.size();
        DisjointSet ds(n);
        unordered_map<string, int> mapMailNode;

        // Step 1: Map emails to account nodes and union overlapping accounts
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < details[i].size(); j++) {
                string mail = details[i][j];
                if (mapMailNode.find(mail) == mapMailNode.end()) {
                    mapMailNode[mail] = i;
                } else {
                    ds.unionBySize(i, mapMailNode[mail]);
                }
            }
        }

        // Step 2: Group emails together by their ultimate parent node
        vector<string> mergedMail[n];
        for (auto it : mapMailNode) {
            string mail = it.first;
            int node = ds.findUPar(it.second);
            mergedMail[node].push_back(mail);
        }

        // Step 3: Sort emails and format the final answer
        vector<vector<string>> ans;
        for (int i = 0; i < n; i++) {
            if (mergedMail[i].size() == 0) continue;
            sort(mergedMail[i].begin(), mergedMail[i].end());
            vector<string> temp;
            temp.push_back(details[i][0]); // Add Name
            for (auto it : mergedMail[i]) {
                temp.push_back(it);        // Add sorted emails
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

8. Summary and Key Takeaways

• Problem Classification: Accounts Merge is a graph connectivity problem efficiently solved using the Disjoint Set Union (DSU) data structure.
• Index-Based DSU: Instead of treating email strings as graph nodes directly, map email strings to their originating account array indices ($0$ to $N-1$).
• Transitive Merging: When a duplicate email is encountered in a new account, performing a unionBySize automatically merges entire component trees.
• Ultimate Parent Routing: During email collection, always query ds.findUPar() to ensure emails map to the root representative of the merged component.
• Lexicographical Ordering: Sorting individual email lists is mandatory before returning the final formatted answer arrays.
• Time Complexity: $\mathcal{O}(N \cdot K \cdot \alpha(N) + \text{sorting})$, where $N$ is the number of accounts, $K$ is the maximum number of emails per account, and $\alpha$ is the Inverse Ackermann function (nearly constant time).