Solution: Accounts Merge

Statement#

You are given a 2D array, accounts, where each row, accounts[i], is an array of strings, such that the first element, accounts[i][0], is a name, while the remaining elements are emails associated with that account. Your task is to determine if two accounts belong to the same person by checking if both accounts have the same name and at least one common email address.

If two accounts have the same name, they might belong to different people since people can have the same name. However, all accounts that belong to one person will have the same name. This implies that a single person can hold multiple accounts.

The output should be a 2D array in which the first element of each row is the name, and the rest of the elements are the merged list of that user’s email addresses in sorted order. There should be one row for each distinct user, and for each user, each email address should be listed only once.

Note: Please use a sort function that sorts the email addresses based on the ASCII value of each character.

Constraints:

• $1 <=$ accounts.length $<= 1000$

• $2 <=$ accounts[i].length $<= 10$

• $1 <=$ accounts[i][j].length $<= 30$

• Because accounts[i][0] is the name of any person, it should contain only English letters.

• For $j>0$, accounts[i][j] should be a valid email.

Solution#

Since the problem involves merging the accounts that have common emails among them, we'll use the union find pattern to solve it. The union find pattern is used to group elements into sets based on a specified property. Each set forms a tree data structure and has a representative element that resides at the root of the tree. The pattern uses a disjoint set data structure, such as an array, to keep track of the membership of each element in the set.

To use the union find pattern, we create and use the UnionFind class, which has two primary methods:

• find(node): Returns the set’s main representative, the root parent, of a given node.

• union(node1, node2): Merges the sets of node1 and node2 into one.

First, we assign a unique ID (an integer value) to each account, making them the representative of their sets. For example, if we have the accounts = $[ ~[Emma, ~e@mail.com], ~[Bob, ~b@mail.com], ~[Emma, ~e2@mail.com, ~e@mail.com] ~]$, we assign them the IDs $0$, $1$, and $2$. We create an array to store these IDs, that is, parents = $[0,~1,~2]$.

Next, we iterate over the given accounts, and for each account, we iterate over its associated emails and map them to one of the parents. If an email is seen for the first time, it gets the ID of its current parent. However, if the email is being seen for the second time, that is, if two accounts share the same email, we take the union of this email’s previously assigned ID and its current ID to make a connection between them. For example, for accounts = $[ ~[Emma, ~e@mail.com], ~[Bob, ~b@mail.com], ~[Emma, ~e2@mail.com, ~e@mail.com] ~]$, we assign $e@mail.com$ the ID of its current parent, $Emma$ (that is, $0$) when we encounter it for the first time. When we see it for the second time, we take the union, such as union(0,2), where $0$ is its previously assigned ID, and $2$ is its current ID. Here, we connect the two accounts because they share the same email. This will eventually change the ID of the second $Emma$ account to the first $Emma$ account such that now, parents = $[0,~1,~0]$, representing that both accounts belong to the same person.

After the mapping above, we merge all the accounts sharing emails into single accounts. To achieve this, we use find(node) for each email to check who is the root parent of the given node. Finally, we go over each account and sort the emails within that account. According to our example, the final merged accounts will look like this: $[ ~[Emma, ~e@mail.com, ~e2@mail.com], ~[Bob, ~b@mail.com] ~]$.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s have a look at the code for the algorithm we just discussed.

Time complexity#

Finding the root parents of all the emails to merge them will take $O(nk.α(n))$, where $α$ is the inverse Ackermann function that grows very slowly, $n$ is the total number of accounts, and $k$ is the maximum number of elements in any account. Sorting all the emails in each account takes $O(nk.log(nk))$. Therefore, the overall time complexity for this solution is $O(nk.α(n)) + O(nk.log(nk))$.

Space complexity#

The space complexity for this solution is $O(nk)$.