Accounts Merge
Combine account records that share an email address into one record per person. A connected-components problem, usually solved with union-find. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a list of accounts. Each account is an array whose first element is a person's name and whose remaining elements are email addresses.
Two accounts belong to the same person if they share at least one email, and this links transitively: if A shares an email with B, and B shares one with C, then A, B and C are all the same person. Two accounts with the same name but no chain of shared emails are different people.
Merge the accounts and return one entry per person: the name, followed by every email that person owns, sorted in ascending (character code) order with no duplicates. The merged accounts may be returned in any order.
Example 1
- Input
- accounts = [["Ola", "ola@a.com", "ola@b.com"], ["Ola", "ola@c.com", "ola@a.com"], ["Ola", "ola@z.com"]]
- Output
- [["Ola", "ola@a.com", "ola@b.com", "ola@c.com"], ["Ola", "ola@z.com"]]
The first two share ola@a.com. The third shares nothing, so it is a different Ola.
Example 2
- Input
- accounts = [["Ian", "i1@x.org"], ["Jo", "j@x.org"], ["Ian", "i2@x.org", "i1@x.org"]]
- Output
- [["Ian", "i1@x.org", "i2@x.org"], ["Jo", "j@x.org"]]
Example 3
- Input
- accounts = [["Pat", "p@m.net", "p@m.net"]]
- Output
- [["Pat", "p@m.net"]]
Duplicate emails within one account appear once.
Constraints
- 1 ≤ accounts.length ≤ 1000
- 2 ≤ accounts[i].length ≤ 10
- Names and emails are 1 to 30 characters.
- Accounts that share an email always have the same name.
Practice
Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Accounts Merge in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Accounts Merge
Pattern: Union-find over shared keys
Picture every email as a node, and connect the emails that appear in the same account. Each person is then one connected component, and the answer is the list of components with their emails sorted.
The trap is the transitive link: accounts can connect through a third account that appears later in the list, so a single left-to-right pass that merges into "the first matching account" misses connections. Union-find handles this directly: for each account, union every email with the account's first email. Afterwards, group emails by their root.
Approach 1: Repeated pairwise merging
Keep merging any two accounts whose email sets intersect until no pair does. Easy to reason about, but each round compares every pair, and a long chain needs many rounds.
Time O(n² · k) per round, up to n rounds · Space O(n · k)
Approach 2: Graph of emails + DFS
Build an adjacency list linking each account's first email to its other emails. Run DFS from every unvisited email to collect its component, then sort it and attach the owner's name.
Time O(E log E) for E total emails · Space O(E)
Approach 3: Union-find on emails
- Map each email to an id and remember the name of an account that contains it.
- For each account, union every email with the account's first email.
- Group emails by
find(email). - For each group, sort the emails and prepend the name.
Path compression keeps each find nearly constant time, so sorting dominates.
Time O(E log E) · Space O(E)
| Approach | Time | Space |
|---|---|---|
| Repeated pairwise merging | O(n² · k) per round, up to n rounds | O(n · k) |
| Graph of emails + DFS | O(E log E) for E total emails | O(E) |
| Union-find on emails | O(E log E) | O(E) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Accounts Merge solution in Python
def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
parent = {}
owner = {}
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root: # path compression
parent[x], x = root, parent[x]
return root
for name, *emails in accounts:
for e in emails:
if e not in parent:
parent[e] = e
owner[e] = name
first = find(emails[0])
for e in emails[1:]:
root = find(e)
if root != first:
parent[root] = first
groups = {}
for e in parent:
groups.setdefault(find(e), []).append(e)
return [[owner[root], *sorted(emails)] for root, emails in groups.items()]Accounts Merge solution in JavaScript
function accountsMerge(accounts) {
const parent = new Map();
const owner = new Map();
const find = (x) => {
let root = x;
while (parent.get(root) !== root) root = parent.get(root);
while (parent.get(x) !== root) {
const next = parent.get(x);
parent.set(x, root); // path compression
x = next;
}
return root;
};
for (const [name, ...emails] of accounts) {
for (const e of emails) {
if (!parent.has(e)) {
parent.set(e, e);
owner.set(e, name);
}
}
for (const e of emails.slice(1)) {
const a = find(emails[0]);
const b = find(e);
if (a !== b) parent.set(b, a);
}
}
const groups = new Map();
for (const e of parent.keys()) {
const root = find(e);
if (!groups.has(root)) groups.set(root, []);
groups.get(root).push(e);
}
const byCode = (a, b) => (a < b ? -1 : a > b ? 1 : 0);
return [...groups].map(([root, emails]) => [owner.get(root), ...emails.sort(byCode)]);
}Common mistakes
- Merging by name. Two people can share a name and have nothing else in common.
- A single pass that only merges into earlier accounts, which misses links that arrive later in the list.
- Keeping duplicate emails when the same address appears in several accounts or twice in one.
- Recursive DFS or recursive find on a long chain, which can blow the call stack. Use an explicit stack or iterative path compression.
- Forgetting to sort the emails, or sorting the name in with them.
What interviewers look for
Name the model early: "emails are nodes, accounts are edges, people are connected components." Once you say that, either DFS or union-find is a natural fit, and interviewers mostly want to see that you got there.
If you pick union-find, explain why you union with the account's first email (it links all of that account's emails with k - 1 unions instead of k²). Mention path compression and that sorting each component is the real cost.
Follow-up questions
What if accounts arrive one at a time and you must report the number of distinct people after each?
Union-find is ideal: keep a component count, add 1 for each new email, and subtract 1 on every union that actually joins two different roots. Each update is nearly O(1) amortized.
How would you scale this to billions of records?
Run connected components in a distributed framework (for example iterative label propagation where each email takes the smallest id among its neighbours until nothing changes). Shard by email hash, and only sort emails per component at the end.
What if two accounts sharing an email could have different names?
Decide a rule with the interviewer, such as the most common name in the component or the name of the earliest account. The grouping itself does not change, only how you label each component.
Companies that ask Accounts Merge
Accounts Merge is tagged by 108 companies in our interview dataset. The score shows how often it comes up at each company.
- Snapchat100%
- Cargurus100%
- Fujitsu100%
- Ingram Micro100%
- Optym93%
- Elastic85%
- League84%
- Freelancercom83%
- Grab82.9%
- Mixi82%
- Logmein82%
- Skyworks Solutions82%
- Kohls82%
- Addepar81%
- Offerup80%
- Embark Studios78%
- Yext78%
- Pagerduty77%
- Figma77%
- Baxter International75%
- 1mg75%
- Crispr Therapeutics74%
- Charles Schwab73%
- Arcus Biosciences71%
and 84 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required