Accounts Merge

The problem description can be found in LeetCode.

Approach

This is an implicit Graph problem. In particular, we need to find a way to connect these emails based on some logic.

In fact, at first, we don't care about the name of the account. We just want to group these emails. Eventually, each group of emails will belong to a certain account.

First, we build the Adjacency List based on the emails. Secondly, we perform a DFS to iterate over this sub-groups.

Solution

from collections import defaultdict
from typing import DefaultDict, List, Set


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        graph = self.get_adjacency_list(accounts)

        return self.group_emails(accounts, graph)

    def get_adjacency_list(
        self, accounts: List[List[str]]
    ) -> DefaultDict[str, List[str]]:
        graph = defaultdict(list)

        for account in accounts:
            emails = account[1:]
            assert len(emails) > 0

            first_email = emails[0]
            for email in emails[1:]:
                graph[first_email].append(email)
                graph[email].append(first_email)

        return graph

    def group_emails(
        self, accounts: List[List[str]], graph: DefaultDict[str, List[str]]
    ) -> List[List[str]]:
        visited: Set[str] = set()
        ans = []

        for account in accounts:
            name = account[0]
            first_email = account[1]

            if first_email in visited:
                continue

            emails: List[str] = []
            self.dfs(graph, first_email, emails, visited)

            emails.sort()
            ans.append([name] + emails)

        return ans

    def dfs(
        self,
        graph: DefaultDict[str, List[str]],
        email: str,
        emails: List[str],
        visited: Set[str],
    ) -> None:
        if email in visited:
            return

        visited.add(email)
        emails.append(email)
        for neighbor in graph[email]:
            self.dfs(graph, neighbor, emails, visited)

Complexity

• Time: $O(nmlognm)$
• Space: $O(nm)$

Where $n$ and $m$ are the number of accounts and the maximum length of a certain account, respectively.