Accounts Merge

19 October 2024 — approx 4 min read.

Given a list of accounts belonging to a user, merge the accounts if they have at least one common email.

Problem Statement

LeetCode-721: 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.

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

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

Approach

Let’s list down a few observations before we start solving the problem:

If two accounts have at least one common email, they belong to the same person and can be merged.
The common email may not be the first email in the list.
There can be duplicate emails in the list.
There can be duplicate accounts in the list.

From the problem description, it is clear that we need to find the connected components in the graph where each node represents an email and the edges represent the common email between two accounts.

We can use DFS - depth-first search to find the connected components in the graph. We can start by creating a graph where each node represents an email and the edges represent the common email between two accounts. We can then traverse the graph using DFS to find the connected components.

Create a graph where each node represents an email and the edges represent the common email between two accounts.
Traverse the graph using DFS to find the connected components.
Merge the connected components and sort the emails in each component.
Return the merged accounts.

Implementation

Here is a Java implementation of the approach:

private final Map<String, List<String>> neighbors = new HashMap<>();
private final Set<String> visited = new HashSet<>();

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    for(List<String> account : accounts){
        // the first entry is the name, so we start from the second entry
        // create a star graph where the first email is connected to all other emails
        // and all other emails are connected to the first email
        String firstEmail = account.get(1);
        for(int i=2; i < account.size(); i++){
            String email = account.get(i);
            neighbors.computeIfAbsent(firstEmail, k -> new ArrayList<>()).add(email);
            neighbors.computeIfAbsent(email, k -> new ArrayList<>()).add(firstEmail);
        }
    }

    List<List<String>> result = new ArrayList<>();
    for(List<String> account : accounts){
        String firstEmail = account.get(1);
        List<String> mergedEmails = new ArrayList<>();

        // if the first email is not already visited, 
        // then it is a new account
        // we need to merge the emails in the connected component
        if(!visited.contains(firstEmail)){
            dfs(mergedEmails, firstEmail);
            Collections.sort(mergedEmails);
            
            // add the name to the merged emails
            // at the beginning of the list
            mergedEmails.add(0, account.get(0));
            result.add(mergedEmails);
        }
    }
    return result;
}

private void dfs(List<String> emails, String email){
    // mark the email as visited
    visited.add(email);
    // add the email to the merged emails
    emails.add(email);

    if(neighbors.containsKey(email)){
        // traverse the neighbors
        // if the neighbor is not visited, then visit it
        // which in turn will visit its neighbors
        // and so on thus forming a connected component
        // and merging the emails in the connected component
        for(String neighbor : neighbors.get(email)){
            if(!visited.contains(neighbor)){
                dfs(emails, neighbor);
            }
        }
    }
}

Complexity Analysis

The time complexity for this approach is $O(N \times M \times \log{M})$, where:

$N$ is the number of accounts
$M$ is the average number of emails in each account.

As we are traversing all the accounts and for each account, we are traversing all the emails in the account and sorting them. The space complexity is $O(N \times M)$.

@dsadaily

Accounts Merge

Problem Statement

Approach

Account Merge Example

Implementation

Complexity Analysis

See Also