Merge Accounts
Medium · Arrays & Hashing · Array · Hash Table · String · Union Find · Depth-First Search · Sorting
Problem
You are given a list accounts. Each accounts[i] is a list whose first element is a name and whose other elements are email addresses of that account.
Two accounts belong to the same person when they share at least one email address, and this is transitive: if A shares an email with B and B with C, all three are one person. Two accounts with the same name are not necessarily the same person, because different people can share a name. All accounts of one person carry the same name.
Merge the accounts and return one entry per person in the form [name, email1, email2, ...], with that person's distinct emails sorted in ascending order. The people themselves may be listed in any order.
Examples
Input: accounts = [["Ana","ana@x.io","a.k@y.io"],["Ben","ben@z.io"],["Ana","a.k@y.io","ana99@q.io"]] Output: [["Ana","a.k@y.io","ana99@q.io","ana@x.io"],["Ben","ben@z.io"]]
The two Ana accounts share "a.k@y.io", so they merge into one sorted list.
Input: accounts = [["Sam","s1@m.io"],["Sam","s2@m.io"]] Output: [["Sam","s1@m.io"],["Sam","s2@m.io"]]
The two accounts share a name but no email, so they are two different people.
Input: accounts = [["Kim","k1@a.io","k2@a.io"],["Kim","k3@a.io"],["Kim","k3@a.io","k2@a.io"]] Output: [["Kim","k1@a.io","k2@a.io","k3@a.io"]]
The first and second accounts share nothing directly, but the third links them through k2 and k3.
Constraints
- 1 <= len(accounts) <= 1000
- 2 <= len(accounts[i]) <= 10
- 1 <= len(accounts[i][j]) <= 30
- Names contain only English letters
- Emails contain lowercase letters, digits, . and one @
Approaches
- Fold each account into the groups it touches — time O(n² · k), space O(N)
Follow-up
What if accounts arrive one at a time and you must answer "how many people so far?" after each? Union-find handles that online: keep a counter that rises with each new email and falls with each successful union.
Related problems
Start free on Cariara · Coding problems · System design studio
