New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Accounts Merge

Contributed by

Dhruv Sharma

Last Updated: 23 Feb, 2023

Hard

0/120

Avg time to solve 15 mins

Success Rate 85 %

1 upvotes

Problem Statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4
Rahul rahul1@gmail.com rahul2@gmail.com 
Amit amit1@gmail.com
Ankur ankur9773@yahoo.com
Rahul rahul1@gmail.com rahul1998@yahoo.com
2
John john2020@gmail.com
Marry mary@outlook.com

Sample output 1 :

3
Rahul rahul1998@yahoo.com rahul1@gmail.com rahul2@gmail.com
Amit amit1@gmail.com
Ankur ankur9773@gmail.com
2
John john2020@gmail.com
Marry mary@outlook.com

Explanation of Sample output 1 :

For the first test case, the first and fourth Rahul’s are the same person as they have a shared email address “rahul1@gmail.com”. The rest of the accounts are of different persons as they don’t share any shared email addresses. So, we merge the first and fourth account.

For the second test case, none of the accounts shares any shared email address.

Sample Input 2 :

2
2
Atul atul@mail.com
Atul atul1@mail.com
1
Bhavani bhavani@mail.com

Sample output 2 :

2
Atul atul1@mail.com 
Atul atul@mail.com 
1
Bhavani bhavani@mail.com

Explanation of Sample output 2 :

For the first test case, the first and second Atul are two different people since they don’t have any common email addresses.

For the second test case, there is only one account. So merging is not required.

Autocomplete

Console