algoadvance

Leetcode 721. Accounts Merge

Problem Statement:

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we want to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. Accounts themselves can be returned in any order.

Example:

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

Clarifying Questions:

  1. Q: How do we handle if the input format is invalid? A: Assume the input is always valid as per the problem description.

  2. Q: Are the email addresses guaranteed to be unique except for the association cases? A: Yes, email addresses uniquely identify a person’s account and thus are used to merge accounts.

Strategy:

  1. Use a Union-Find Data Structure: This will help efficiently group emails that belong to the same account.
  2. Map Emails to Names: Use a hash map to associate each email with its corresponding name.
  3. Group Emails: Use the union-find structure to group all emails, then iterate through the union-find structure to aggregate emails by their root parent.
  4. Sort and Format the Output: For each group of emails (i.e., an account), sort the emails alphabetically and add the corresponding name before returning the formatted list.

Code:

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class UnionFind {
public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 1);
        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 union_sets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY])
                swap(rootX, rootY);
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY])
                ++rank[rootX];
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, int> email_to_id;
    unordered_map<int, string> id_to_name;
    int id = 0;

    // Assign IDs to each email and store corresponding names
    for (const auto& account : accounts) {
        string name = account[0];
        for (int i = 1; i < account.size(); ++i) {
            if (email_to_id.find(account[i]) == email_to_id.end()) {
                email_to_id[account[i]] = id++;
                id_to_name[email_to_id[account[i]]] = name;
            }
        }
    }

    // Initialize Union-Find structure
    UnionFind uf(id);

    // Union emails within the same account
    for (const auto& account : accounts) {
        for (int i = 2; i < account.size(); ++i) {
            uf.union_sets(email_to_id[account[1]], email_to_id[account[i]]);
        }
    }

    // Group emails by their root parent
    unordered_map<int, unordered_set<string>> grouped_emails;
    for (const auto& [email, id] : email_to_id) {
        int root_id = uf.find(id);
        grouped_emails[root_id].insert(email);
    }

    // Format the output
    vector<vector<string>> merged_accounts;
    for (const auto& [root_id, emails] : grouped_emails) {
        vector<string> account(emails.begin(), emails.end());
        sort(account.begin(), account.end());
        account.insert(account.begin(), id_to_name[root_id]);
        merged_accounts.push_back(account);
    }

    return merged_accounts;
}

Time Complexity:

The overall complexity can be considered efficient for the problem size as it uses efficient data structures for set operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI