721. Accounts Merge
Asked at Oracle, Ripple, Goldman Sachs
Difficulty
Medium
Time
O(n * k * α(n * k))
Space
O(n * k)
Pattern
Array
Companies
3
Problem
You get a list of accounts. Each account is a list of strings. The first string is a name, and the remaining strings are emails that belong to that account.
Two accounts belong to the same person if they share at least one email. When that happens, merge them into one account. Be careful: two accounts with the same name are not automatically the same person, because different people can have the same name. Also, all accounts of one person always use the same name.
Return the merged accounts. Each merged account starts with the person's name, followed by all of that person's emails in sorted order with no duplicates. The order of the accounts in the result does not matter.
Which accounts are the same person?
Constraints
- ●
1 <= accounts.length <= 1000 - ●
2 <= accounts[i].length <= 10 - ●
1 <= accounts[i][j].length <= 30 - ●
accounts[i][0] consists of English letters - ●
accounts[i][j] (for j > 0) is a valid email
Examples
accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]][["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]"[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","Kevin5@m.Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Ripple | Medium | View all Ripple questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Union-Find approach: treat each email as a node. For each account, union all emails together. After processing all accounts, emails in the same connected component belong to the same person. Group emails by their root, sort them, and attach the name.
Why Union-Find: account 0 has emails [a, b], account 1 has [b, c], account 2 has [d]. Union: a-b, b-c. a, b, c are in one component. d is separate. Result: merge accounts 0 and 1.
DFS/BFS approach: build a graph where each email maps to its account name. For each email, if it has been seen in another account, mark them as connected. Run DFS to find connected components of emails. Assign the name from the first email in each component.
Complexity: Union-Find with path compression and union by rank is nearly O(1) per operation. Total: O(n * k * alpha(n*k)) where n = accounts, k = avg emails per account. DFS: O(n * k) to build graph and traverse.
Optimal Approach
Union-Find: assign each unique email an integer ID. For each account, union all emails together (they belong to the same person). After processing, group emails by their root parent. For each group, sort the emails and attach the account name.
Walkthrough with [["John","a@","b@"], ["John","b@","c@"], ["Mary","d@"]]:
- Assign IDs: a@=0, b@=1, c@=2, d@=3
- Account 0: union(0, 1). Components: {0,1}, {2}, {3}
- Account 1: union(1, 2). Components: {0,1,2}, {3}
- Account 2: no union needed. Components: {0,1,2}, {3}
- Group by root: {a@, b@, c@} -> name "John", {d@} -> name "Mary"
- Sort each group: ["a@","b@","c@"], ["d@"]
- Result: [["John","a@","b@","c@"], ["Mary","d@"]]
Time: O(n * k * alpha(n*k)). Space: O(n * k).
Union-Find over emails
What Trips People Up in Real Interviews
Not sorting the emails in the result. The problem requires sorted unique emails in each merged account. Always sort before returning.
Forgetting that the same email can appear in multiple accounts. That is the entire point of merging. The Union-Find or DFS handles this by grouping emails across accounts.
Using account indices for Union-Find instead of email-to-index mapping. You need to map each email to a node index. Use a hash map: email -> unique integer id.
Not handling the name correctly. If two accounts have the same emails but different names, the problem guarantees this will not happen. But if it did, you would need to decide which name to use.
Forgetting to deduplicate emails. The same email might appear multiple times within one account. Use a set before unioning or use unique emails only.
Solution Code
O(n * k * α(n * k)) timeclass UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
def accountsMerge(accounts):
email_to_id = {}
email_to_name = {}
uid = 0
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = uid
uid += 1
email_to_name[email] = name
uf = UnionFind(uid)
for account in accounts:
emails = account[1:]
for i in range(1, len(emails)):
uf.union(email_to_id[emails[0]], email_to_id[emails[i]])
from collections import defaultdict
groups = defaultdict(list)
for email, eid in email_to_id.items():
root = uf.find(eid)
groups[root].append(email)
result = []
for emails in groups.values():
result.append([email_to_name[emails[0]]] + sorted(emails))
return resultFrequently Asked Questions
What is the Accounts Merge problem?
Given a list of accounts where each account has a name and a list of emails, merge accounts that share at least one common email. Return the merged accounts with sorted unique emails. This is a classic Union-Find / connected components problem.
How do you solve Accounts Merge?
The optimal approach runs in O(n * k * α(n * k)) time and O(n * k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Accounts Merge?
Accounts Merge is asked at Oracle, Ripple, Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Accounts Merge?
- Not sorting the emails in the result. The problem requires sorted unique emails in each merged account. Always sort before returning.
- Forgetting that the same email can appear in multiple accounts. That is the entire point of merging. The Union-Find or DFS handles this by grouping emails across accounts.
- Using account indices for Union-Find instead of email-to-index mapping. You need to map each email to a node index. Use a hash map: email -> unique integer id.
- Not handling the name correctly. If two accounts have the same emails but different names, the problem guarantees this will not happen. But if it did, you would need to decide which name to use.
- Forgetting to deduplicate emails. The same email might appear multiple times within one account. Use a set before unioning or use unique emails only.