Accounts Merge
Asked at Oracle, Ripple
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Ripple | Medium | View all Ripple 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.
Visual walkthrough for accounts = [["John","a@","b@"], ["John","b@","c@"], ["Mary","d@"]]:
Email graph: a@ -> John, b@ -> John (from account 0) b@ -> John, c@ -> John (from account 1)
d@ -> Mary (from account 2)
Union-Find: union(a@, b@), union(b@, c@). Components: {a@,b@,c@}, {d@}
Result: [["John","a@","b@","c@"], ["Mary","d@"]]
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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Accounts Merge?
Accounts Merge is asked at Oracle, Ripple. 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.