How do you solve Accounts Merge on LeetCode?

Accounts Merge (LeetCode #721) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + e), where n is the number of accounts and e is the number of emails. time complexity and O(n + e) space complexity. Key insight: Understanding the relationship between emails is crucial; they form a graph where merging accounts is about finding connected components.

What is the time complexity of Accounts Merge?

The optimal solution for Accounts Merge runs in O(n + e), where n is the number of accounts and e is the number of emails. time and uses O(n + e) space. This complexity is due to the graph traversal, where we visit each email and its connections.

What is the brute force solution for Accounts Merge?

The brute force approach for Accounts Merge is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check each account against every other account to find common emails. If two accounts share an email, we merge them. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n + e), where n is the number of accounts and e is the number of emails..

What are the interview tips for Accounts Merge?

Always clarify the problem requirements and constraints before jumping into coding. Think about edge cases, such as accounts with no emails or completely separate accounts. Practice explaining your thought process and approach as you code to demonstrate your understanding.

What are common mistakes when solving Accounts Merge?

Failing to handle duplicate emails within the same account. Not considering the case where accounts have the same name but are different people.

#721

Accounts Merge

Medium

ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSortingGraph Traversal (DFS, BFS)Union-Find

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + e), where n is the number of accounts and e is the number of emails.
Space	O(1)	O(n + e)

💡

Intuition

Time O(n + e), where n is the number of accounts and e is the number of emails.Space O(n + e)

We can model this problem as a graph where emails are nodes and edges exist between emails that belong to the same account. Using DFS or Union-Find, we can efficiently find connected components.

⚙️

Algorithm

3 steps

1Step 1: Create a graph where each email is a node and edges connect emails from the same account.
2Step 2: Use DFS or Union-Find to find connected components of emails.
3Step 3: For each connected component, collect emails, sort them, and prepend the account name.

solution.py29 lines

1from collections import defaultdict
2
3def accountsMerge(accounts):
4    graph = defaultdict(set)
5    for account in accounts:
6        name = account[0]
7        for i in range(2, len(account)):
8            graph[account[i]].add(account[i-1])
9            graph[account[i-1]].add(account[i])
10    visited = set()
11    merged_accounts = []
12
13    def dfs(email):
14        stack = [email]
15        component = []
16        while stack:
17            node = stack.pop()
18            if node not in visited:
19                visited.add(node)
20                component.append(node)
21                stack.extend(graph[node])
22        return component
23
24    for account in accounts:
25        for email in account[1:]:
26            if email not in visited:
27                component = dfs(email)
28                merged_accounts.append([account[0]] + sorted(component))
29    return merged_accounts

ℹ

Complexity note: This complexity is due to the graph traversal, where we visit each email and its connections.

1Understanding the relationship between emails is crucial; they form a graph where merging accounts is about finding connected components.
2Using graph traversal techniques like DFS or Union-Find can significantly optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.