You are given a list of accounts, each a comma-joined string "name,email1,email2,...". Two accounts belong to the same person if they share at least one email (names may repeat across different people). Merge them: each merged account is "name,<emails>" where the emails are unique and sorted, and the name is taken from the merged group. Return the list of merged accounts (order does not matter).
(To keep I/O simple each account is a single comma-separated string with no spaces; the group's name is taken from its smallest-index original account.)
Input: accounts = ["john,a,b", "john,b,c", "mary,d"] Output: ["john,a,b,c", "mary,d"] The two john accounts share email b, so they merge; mary is separate.
Input: accounts = ["p,e1", "q,e2", "r,e1"] Output: ["p,e1", "q,e2"] p and r share e1 and merge (keeping the smaller-index name p); q stands alone.
- 1 <= accounts.length <= 1000 - each account has a name and 0+ emails - emails and names contain no spaces
Two accounts merge when they share an email, and merging is transitive (A shares with B, B with C ⇒ all three are one person). That's a connected-components problem where accounts are nodes and a shared email is an edge.
Two ways to find the components:
Union-Find. Keep a map email → first account that owned it. For each account's emails, if an email was seen before, union this account with that first owner; otherwise record the owner. Accounts in the same set are one person. O(total-emails · α).
DFS. Group account indices by email, connect all accounts sharing each email, and DFS the resulting graph for components.
Either way, for each component gather its unique emails, sorted, prefix the name, and emit. O(N·K log K) for the sorting, where K is the emails per group.
“What links two accounts?”
Any common email (not the name).
“How are emails output?”
Unique and sorted, with the name first.
Accounts sharing an email are the same person, so it's connected components over an email-sharing graph.
I union accounts through a first-owner map per email, then output each group's sorted unique emails.
Worked example — ["john,a,b", "john,b,c", "mary,d"]
account 1 shares email b with account 0 -> merge {0,1}
result: "john,a,b,c" and "mary,d"
Names don't link accounts.
No explicit pairwise graph needed.
Then prefix the name.
| DFS on email graph | Union-Find | |
|---|---|---|
| Grouping | connect accounts per email, DFS | merge via first-owner map |
| Time | O(sum emails) | O(sum emails · α) |
| Output | sorted emails per group | sorted emails per group |
Both find the same groups and produce the same merged accounts. Full code is in the Approaches selector below.
Key takeaway
Accounts sharing an email are one person (transitively) — a connected-components problem. Union accounts via a first-owner-per-email map (or DFS the email graph), then emit each group's sorted unique emails with the name.
for each email: union this account with its first owner per component: name + sorted(unique emails)