Accounts Merge

Posted: 11 Jan, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You have been given an array/list 'ACCOUNTS' where each element, i.e. ACCOUNTS[i] contains a list of strings, where the first element is the name of the account holder and the rest of the strings are emails representing the emails of the account.

Now, you are supposed to merge the accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that it may be possible that two accounts belong to the same name, but they may belong to different people as people could have the same name. And a person could have any number of accounts initially, but all their accounts definitely have the same name.

After merging the accounts, you have to return an array/list of merged accounts where each account, the first element is the name of the person, and the rest elements are the email addresses in sorted order (non-decreasing). Accounts themselves can be in any order.

Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer ‘N’ denoting the number of accounts.

Each of the next ‘N’ lines contains space-separated strings where the first string denotes the account holder’s name, and the rest of the strings represent the email addresses.
Output Format :
For each test case, print the number of accounts after merging in the first line and then print the space-separated name and email address associated with each account in a separate line.

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 100
1 <= |accounts[i]| <= 10
1 <= |accounts[i][j]| <= 30

Time limit: 1 sec
Approach 1

The basic idea of this approach is to model this problem as a graph problem. Let us create a graph of emails with an edge between two emails if they occur in the same account. 

 

The figure below shows the graph constructed for the first test case of sample test case 1.

 

 

We can observe that the set of accounts which needs to be merged will be a part of connected components. So the problem is now reduced to finding the connected components in an undirected graph. We can easily get the connected component by doing a depth-first search of the graph. You can refer to this tutorial of cp-algorithms for a more detailed explanation. Search for connected components in a graph - https://cp-algorithms.com/graph/search-for-connected-components.html#:~:text=Given%20an%20undirected%20graph%20G,path%20exists%20between%20different%20groups.

 

Let unordered_map<string, string> ‘EMAIL_TO_NAME’ be HashMap to store the mapping of emails to the name of the person having it. This mapping will help us in getting the name of the person while creating the merged accounts.

 

And also let unorderd_map<string, vector<string>> ‘GRAPH’ stores the adjacency list of the constructed graph.

 

Now the consider the following steps :

  1. Iterate through each ‘ACCOUNT’ in the array/list of ‘ACCOUNTS'. And for each ‘ACCOUNT’:
    • Store the mapping of email to the name for each email address.
    • And also create an edge between the first email address and the rest of the email address.
  2. Now create a set<string> ‘VISITED’ which stores the email address which is visited during the depth-first search. Also, create a vector<vector<string>> ‘MERGED_ACCOUNTS’ to store the name and email addresses of the merged accounts.
  3. Now, start doing the depth-first search from each non-visited email address.
    • And store the email addresses belonging to the current connected component in a new array/list.
    • Insert the name of the person having the email addresses in a new array/list ‘ACCOUNT’ and then insert all the addresses. Then, insert the current account details into the ‘MERGED_ACCOUNTS’.
Try Problem