Accounts Merge medium

Problem Statement

Given a list of accounts where each account contains a name and a list of email addresses, merge accounts with common email addresses. The accounts may have different names, but they should be merged into a single account containing all the email addresses. The output should be a list of merged accounts, where each account has a unique name (you can use any name from the input accounts) and a sorted list of unique email addresses.

Example 1

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

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

Explanation: The first two accounts both contain "john00@mail.com", so they are merged.

Example 2

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]

Output: [["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Steps

1. Build a graph: Create a graph where each email address is a node. An edge connects two email addresses if they belong to the same account.

2. Perform Depth-First Search (DFS): Traverse the graph using DFS to find connected components. Each connected component represents a merged account.

3. Merge accounts: For each connected component, collect all email addresses and a name (from any account in the component). Sort the email addresses.

4. Return the result: Return the list of merged accounts.

Explanation

The key idea is to use a graph to represent the relationships between email addresses. If two email addresses appear in the same account, they are connected. Finding connected components in this graph efficiently identifies the groups of email addresses that need to be merged. DFS is a well-suited algorithm for finding connected components.

Code

function accountsMerge(accounts: string[][]): string[][] {
    const graph: Map<string, Set<string>> = new Map();
    const nameMap: Map<string, string> = new Map();

    // Build the graph
    for (const account of accounts) {
        const name = account[0];
        for (let i = 1; i < account.length; i++) {
            const email = account[i];
            graph.set(email, graph.get(email) || new Set());
            nameMap.set(email, name); // Store the name associated with each email
            if (i > 1) {
                graph.get(account[i - 1])!.add(email);
                graph.get(email)!.add(account[i - 1]); // Undirected graph
            }
        }
    }


    const visited: Set<string> = new Set();
    const result: string[][] = [];

    // Perform DFS to find connected components
    function dfs(email: string, component: string[]): void {
        visited.add(email);
        component.push(email);
        for (const neighbor of graph.get(email)!) {
            if (!visited.has(neighbor)) {
                dfs(neighbor, component);
            }
        }
    }

    //Iterate through all emails, starting DFS from unvisited ones
    for (const email of graph.keys()){
        if(!visited.has(email)){
            const component: string[] = [];
            dfs(email, component);
            component.sort();
            result.push([nameMap.get(component[0])!, ...component]);
        }
    }

    return result;
}

Complexity

• Time Complexity: O(N log N), where N is the total number of email addresses. This is dominated by the sorting of email addresses in each connected component. Building the graph and performing DFS are both O(N) in the worst case.

• Space Complexity: O(N), primarily due to the graph and the visited set. In the worst case, the graph could contain all email addresses as nodes.