Skip to content

721. Accounts Merge

On LeetCode ->

Problem

Merge accounts connected by at least one shared email, including transitive connections. Return each person's name followed by all unique emails in sorted order; result groups may appear in any order.

Input:  [["John", "a@mail", "b@mail"], ["John", "b@mail", "c@mail"], ["John", "x@mail"]]
Output: [["John", "a@mail", "b@mail", "c@mail"], ["John", "x@mail"]]

Key trick

Treat emails as graph nodes: connect all emails within an account, then each connected component is one merged account.

Trap

  • Comparing accounts only in pairs misses transitive connections.
  • Equal names do not imply equal people.
  • Building every pair of emails creates unnecessary clique edges; connecting each email to one anchor is enough.
  • Emails must be deduplicated and sorted in the result.

Why is it interesting?

It turns a record-merging problem into finding connected components, illustrating transitive identity relationships.

Python solution

class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        graph = {}
        email_name = {}

        for name, *emails in accounts:
            anchor = emails[0]
            email_name[anchor] = name
            graph.setdefault(anchor, set())

            # A star connects the whole account using only linear edges.
            for email in emails[1:]:
                email_name[email] = name
                graph.setdefault(email, set()).add(anchor)
                graph[anchor].add(email)

        res = []
        visited = set()

        for start in graph:
            if start in visited:
                continue

            stack = [start]
            visited.add(start)
            component = []

            # Every connected component represents one person.
            while stack:
                email = stack.pop()
                component.append(email)

                for nei in graph[email]:
                    if nei not in visited:
                        visited.add(nei)
                        stack.append(nei)

            res.append([email_name[start], *sorted(component)])

        return res

Let \(E\) be the total number of email occurrences and \(U\) the number of unique emails.

  • Time: \(O(E + U \log U)\)
  • Space: \(O(E + U)\)

Comment on my solution

Your solution is correct and properly handles transitive merging with iterative DFS.

  • email_name correctly recovers the component's name.
  • Marking emails visited when pushing them prevents repeated traversal.
  • The nested loops connect every pair of emails, producing a clique in \(O(k^2)\) time and space for an account with \(k\) emails.
  • Starting j at i also creates unnecessary self-loops.
  • Connecting every email only to the account's first email preserves connectivity while reducing graph construction to \(O(k)\).
# Ideas:
# - This is a remove duplicate kind of problem
#   - with grouping
#   - and maybe canonicalization
# - two accounts with the same name are the same when they have one
#   email in common.
# - ["john", "a@mail.com", b@mail.com], ["john", "b@mail.com", c@mail.com],
#   ["john", "c@mail.com", d@mail.com]
#   - first john has no email in common with the third john but they are
#     the same john as they have c@mail.com in common with the second john
#   - So a simple interesection check between two group of emails is not
#     enough to detect person duplicate

# First try
#
# Wrong Answer: 25/50 testcases passed
# [["David","David0@m.co","David1@m.co"],
#  ["David","David3@m.co","David4@m.co"],
#  ["David","David4@m.co","David5@m.co"],
#  ["David","David2@m.co","David3@m.co"],
#  ["David","David1@m.co","David2@m.co"]]
# Output: [["David","David0@m.co","David1@m.co","David2@m.co"],["David","David2@m.co","David3@m.co","David4@m.co","David5@m.co"]]
# Expected: [["David","David0@m.co","David1@m.co","David2@m.co","David3@m.co","David4@m.co","David5@m.co"]]
class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        names = {}
        for name, *emails in accounts:
            if name not in names:
                names[name] = [set(emails)]
                continue

            merged = False
            for account_emails in names[name]:
                if len(account_emails.intersection(emails)):
                    merged = True
                    for email in emails:
                        account_emails.add(email)
                    break
            if not merged:
                names[name].append(set(emails))

        res = []
        for name, account_emails in names.items():
            for emails in account_emails:
                res.append([name, *sorted(list(emails))])

        return res

# Second try
#
# WRONG
class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        names = {}
        for name, *emails in accounts:
            names.setdefault(name, []).append(set(emails))

        # NOT ENDED
        # now for each name, we should merge emails which are
        # in the same component in the graph where name are vertices
        # and every groups of emails are links by edges

# Third try
#
# WORKS
class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        email_name = {}
        graph = {}
        for name, *emails in accounts:
            for email in emails:
                email_name[email] = name
            for i in range(len(emails)):
                for j in range(i, len(emails)):
                    graph.setdefault(emails[i], []).append(emails[j])
                    graph.setdefault(emails[j], []).append(emails[i])


        res = []
        visited = set()
        for email in graph:
            if email in visited:
                continue

            # dfs
            stack = [email]
            visited.add(email)
            emails = []

            while stack:
                node_email = stack.pop()
                emails.append(node_email)
                for nei_email in graph[node_email]:
                    if nei_email not in visited:
                        visited.add(nei_email)
                        stack.append(nei_email)
            res.append([email_name[email], *sorted(emails)])

        return res

Extra

What is a clique graph?

A clique is a graph where every node is directly connected to every other node.

For one account:

["John", "a@mail", "b@mail", "c@mail"]

Your nested loops create these useful edges:

a - b
a - c
b - c

They form a clique:

a ----- b
 \     /
  \   /
    c

Your code also creates unnecessary self-loops because j starts at i:

a - a
b - b
c - c

To find connected components, every pair does not need a direct edge. All emails only need to be reachable from each other. A star is sufficient:

a - b
|
c

This can be built by connecting the first email to every other email:

anchor = emails[0]

for email in emails[1:]:
    graph[anchor].append(email)
    graph[email].append(anchor)

For \(k\) emails:

  • Clique: \(\frac{k(k-1)}{2}\) useful edges, so \(O(k^2)\).
  • Star: \(k-1\) edges, so \(O(k)\).

Both produce the same connected component, but the star uses fewer edges.