721. Accounts Merge

Hint - Union Find

class UnionFind {
private:
    // Stores the parent of each node
    // Stores the rank (or depth) of each node

public:
    // Constructor: Initialize parent and rank vectors
    UnionFind()
    {
        // Resize parent vector to hold n elements
        // Initialize rank vector with 1 for all elements
        // Set each node to be its own parent
    }

    // Find the root of the set containing x, with path compression
    int find()
    {
    }

    // Union the sets containing n1 and n2
    void unionNodes()
    {
        // Find the root of the set containing n1
        // Find the root of the set containing n2
        // If they are already in the same set, do nothing

        // Union by rank
        if ()
        {
            // Attach smaller tree to larger tree
        }
        else if ()
        {
            // Attach smaller tree to larger tree
        }
        else
        {
            // Attach second tree to first and increase rank
        }
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts)
    {
        // Number of accounts
        // Create UnionFind instance with n nodes
        // Maps email to account index

        // Iterate through each account
        for ()
        {
            // Iterate through each email in the account
            for ()
            {
                if ()
                {
                    // Union the current account with the account that already has this email
                }
                else
                {
                    // Map the email to the current account index
                }
            }
        }

        // Maps root account index to list of emails
        // Collect emails for each connected component
        for ()
        {
        }

        // Result vector to store merged accounts
        // Prepare the final result
        for ()
        {
            // Get the username
            // Initialize group with the username
            // Sort emails in lexicographical order
            // Add emails to group
            // Add group to result
        }
        // Return the merged accounts
    }
};

• Union Find

class UnionFind {
private:
    vector<int> parent; // Stores the parent of each node
    vector<int> rank;   // Stores the rank (or depth) of each node

public:
    // Constructor: Initialize parent and rank vectors
    UnionFind(int n)
    {
        parent.resize(n); // Resize parent vector to hold n elements
        rank.resize(n, 1); // Initialize rank vector with 1 for all elements
        for (int i = 0; i < n; i++) parent[i] = i; // Set each node to be its own parent
    }

    // Find the root of the set containing x, with path compression
    int find(int x)
    {
        if (x != parent[x])
        {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    // Union the sets containing n1 and n2
    void unionNodes(int n1, int n2)
    {
        int p1 = find(n1); // Find the root of the set containing n1
        int p2 = find(n2); // Find the root of the set containing n2
        if (p1 == p2) return; // If they are already in the same set, do nothing

        // Union by rank
        if (rank[p1] > rank[p2])
        {
            parent[p2] = p1; // Attach smaller tree to larger tree
        }
        else if (rank[p1] < rank[p2])
        {
            parent[p1] = p2; // Attach smaller tree to larger tree
        }
        else
        {
            parent[p2] = p1; // Attach second tree to first and increase rank
            rank[p1]++;
        }
    }
};

class Solution {
public:
    // Merge accounts with the same email
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts)
    {
        int n = accounts.size(); // Number of accounts
        UnionFind uf(n); // Create UnionFind instance with n nodes
        unordered_map<string, int> emailMap; // Maps email to account index

        // Iterate through each account
        for (int i = 0; i < n; i++)
        {
            // Iterate through each email in the account
            for (int j = 1; j < accounts[i].size(); j++)
            {
                string email = accounts[i][j];
                if (emailMap.count(email))
                {
                    // Union the current account with the account that already has this email
                    uf.unionNodes(emailMap[email], i);
                }
                else
                {
                    // Map the email to the current account index
                    emailMap[email] = i;
                }
            }
        }

        unordered_map<int, vector<string>> mergeMap; // Maps root account index to list of emails
        // Collect emails for each connected component
        for (auto& [email, accountIdx] : emailMap)
        {
            mergeMap[uf.find(accountIdx)].push_back(email);
        }

        vector<vector<string>> res; // Result vector to store merged accounts
        // Prepare the final result
        for (auto& [accountIndex, emails] : mergeMap)
        {
            string user = accounts[accountIndex][0]; // Get the username
            vector<string> group = {user}; // Initialize group with the username
            sort(emails.begin(), emails.end()); // Sort emails in lexicographical order
            group.insert(group.end(), emails.begin(), emails.end()); // Add emails to group
            res.push_back(group); // Add group to result
        }

        return res; // Return the merged accounts
    }
};

• T: $O(n \cdot k \cdot \log (n \cdot k))$
• S: $O(n \cdot k)$