Accounts Merge
Accounts Merge:
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 would like 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. The accounts themselves can be returned in any order.
Example 1:
Input: accounts = [["John","[email protected]","[email protected]"],
["John","[email protected]","[email protected]"],
["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],
["Mary","[email protected]"],["John","[email protected]"]]
Explanation:
The first and second John's are the same person as they
have the common email "[email protected]".
The third John and Mary are different people as none of
their email addresses are used by other accounts.
We could return these lists in any order, for example the answer
[['Mary', '[email protected]'], ['John', '[email protected]'],
['John', '[email protected]', '[email protected]', '[email protected]']]
would still be accepted.
Example 2:
Input: accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],
["Kevin","[email protected]","[email protected]","[email protected]"],
["Ethan","[email protected]","[email protected]","[email protected]"],
["Hanzo","[email protected]","[email protected]","[email protected]"],
["Fern","[email protected]","[email protected]","[email protected]"]]
Output: [["Ethan","[email protected]","[email protected]","[email protected]"],
["Gabe","[email protected]","[email protected]","[email protected]"],
["Hanzo","[email protected]","[email protected]","[email protected]"],
["Kevin","[email protected]","[email protected]","[email protected]"],
["Fern","[email protected]","[email protected]","[email protected]"]]
Constraints:
1 <= accounts.length <= 10002 <= accounts[i].length <= 101 <= accounts[i][j].length <= 30accounts[i][0]consists of English letters.accounts[i][j] (for j > 0)is a valid email.
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
int[] parent = new int[accounts.size()];
Arrays.fill(parent, -1);
TreeMap<String, Integer> map = new TreeMap<>();
for(int i = 0; i < accounts.size(); ++i){
for(int j = 1; j < accounts.get(i).size(); ++j){
if(map.containsKey(accounts.get(i).get(j))){
int idx = map.get(accounts.get(i).get(j));
if(idx != i && findParent(parent, i) != findParent(parent, idx)){
union(parent, i, idx);
}
}else{
map.put(accounts.get(i).get(j), i);
}
}
}
Map<Integer, List<String>> mapIndexToEmails = new HashMap<>();
map.entrySet().stream()
.forEach(entry -> {
int idx = findParent(parent, entry.getValue().intValue());
mapIndexToEmails.computeIfAbsent(idx, k -> new ArrayList<String>()).add(entry.getKey());
});
List<List<String>> result = new ArrayList<>();
mapIndexToEmails.entrySet().stream()
.forEach(entry -> {
List<String> emailList = new ArrayList<>();
emailList.add(accounts.get(entry.getKey()).get(0));
emailList.addAll(entry.getValue());
result.add(emailList);
});
return result;
}
private int findParent(int[] parent, int idx){
if(parent[idx] == -1) return idx;
return findParent(parent, parent[idx]);
}
private void union(int parent[], int x, int y)
{
int xset = findParent(parent, x);
int yset = findParent(parent, y);
parent[xset] = yset;
}
}
/**
* @param {string[][]} accounts
* @return {string[][]}
*/
var accountsMerge = function (accounts) {
const parent = new Array(accounts.length).fill(-1);
const map = new Map();
for (let i = 0; i < accounts.length; i++) {
for (let j = 1; j < accounts[i].length; j++) {
if (map.has(accounts[i][j])) {
const idx = map.get(accounts[i][j]);
if (idx !== i && findParent(parent, i) !== findParent(parent, idx)) {
union(parent, i, idx);
}
} else {
map.set(accounts[i][j], i);
}
}
}
const mapIndexToEmails = new Map();
for (const [email, idx] of map.entries()) {
const parentIdx = findParent(parent, idx);
if (!mapIndexToEmails.has(parentIdx)) {
mapIndexToEmails.set(parentIdx, []);
}
mapIndexToEmails.get(parentIdx).push(...accounts[idx].slice(1));
}
const result = [];
for (const [idx, emails] of mapIndexToEmails.entries()) {
const emailList = [accounts[idx][0], ...new Set(emails)];
emailList.sort();
result.push(emailList);
}
return result;
};
function findParent(parent, idx) {
if (parent[idx] === -1) return idx;
return findParent(parent, parent[idx]);
}
function union(parent, x, y) {
const xset = findParent(parent, x);
const yset = findParent(parent, y);
parent[xset] = yset;
}
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
def findParent(parent, idx):
if parent[idx] == -1:
return idx
return findParent(parent, parent[idx])
def union(parent, x, y):
xset = findParent(parent, x)
yset = findParent(parent, y)
parent[xset] = yset
parent = [-1] * len(accounts)
map = {}
for i in range(len(accounts)):
for j in range(1, len(accounts[i])):
if accounts[i][j] in map:
idx = map[accounts[i][j]]
if idx != i and findParent(parent, i) != findParent(parent, idx):
union(parent, i, idx)
else:
map[accounts[i][j]] = i
mapIndexToEmails = {}
for email, idx in map.items():
parentIdx = findParent(parent, idx)
if parentIdx not in mapIndexToEmails:
mapIndexToEmails[parentIdx] = []
mapIndexToEmails[parentIdx].extend(accounts[idx][1:])
result = []
for idx, emails in mapIndexToEmails.items():
emailList = [accounts[idx][0]] + sorted(list(set(emails)))
result.append(emailList)
return result
class Solution {
public:
vector<int> parent;
int find_set(int x){
if(parent[x] == x) return x;
return parent[x] = find_set(parent[x]);
}
void make_union(int x, int y){
int a = find_set(x);
int b = find_set(y);
if(a != b){
parent[a] = b;
}
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
parent.resize(n);
unordered_map<string, int> map;
for(int i = 0; i<n; i++){
parent[i] = i;
for(int j = 1; j<accounts[i].size(); j++){
if(map.find(accounts[i][j]) != map.end()){
make_union(map[accounts[i][j]], i);
}
else{
map[accounts[i][j]] = parent[i];
}
}
}
unordered_map<int, vector<string>> newaccounts;
for(auto it : map){
newaccounts[find_set(it.second)].push_back(it.first);
}
vector<vector<string>> result;
for(auto &it : newaccounts){
auto &emails = it.second;
sort(emails.begin(), emails.end());
emails.insert(emails.begin(), accounts[it.first][0]);
result.push_back(emails);
}
return result;
}
};
Time/Space Complexity:
- Time Complexity: O(e*(l+a(n)+loge))
- Space Complexity: O(e)
Where e is the total number of all email addresses in all accounts, l is the average length of email, n is the number of accounts and
a(n) is inverse Ackermann function that defines time complexity of findParent/union operations.
Explanation:
The function first creates an array called parent and initializes it with the value -1 for every element. This array will be used as a data structure for union-find. We use union find since it's obvious that the records are connected if they share at least one email address, so we could join them into groups with union or disjoint sets operations which are straightforward to implement. It also creates a TreeMap called map, which will be used to map email addresses to the accounts that contain them. We chose TreeMap since it provides out of box sorted order of keys. While we iterate over the emails we check if the address is already present in the map and under which account, if the account that we currently have stored inside the map is different than the current one and if there a disjoint set (findParent(parent, i) != findParent(parent, idx)) we can merge the two disjoint sets by creating their union (merging accounts).
If the email is not already in the map, it adds it to the map with the current account's index.
Afterwards, it creates a map mapIndexToEmails that maps the index of an account to its associated email addresses, merging any accounts that were found to have the same email. Then it constructs the result, which is a list of lists of strings, where each inner list contains the name of the account followed by all its associated email addresses.
The total space complexity is proportional to the number of all email addresses that we need to store. While for the time complexity, for each email address we have the following operations:
- We first must hash a string to put it in a map with the operation taking
O(l)wherelis the average length of an email address - We have operations on treemap which take
O(log e)whereeis the total number of all email addresses in all accounts (also the maximum number of elements in the treemap) - Union and find operations which are defined by inverse Ackermann function
a(n)(strict boundary, for the interview is enough to say the complexity is approximately constant) wherenis the number of accounts This leads to total time complexity ofO(e*(l+a(n)+loge)).
One tricky part to focus on is findParent(parent, i) != findParent(parent, idx) which prevents creating cycles inside the parent array which is tracking the parents of all sets/accounts.