478. Accounts Merge
You are given accounts, a list of account entries. Each entry is a list of strings [name, email1, email2, …]: the owner's name followed by one or more email addresses registered under that entry.
The same person may have created several entries. Two entries belong to the same person exactly when they share at least one email address — and that link is transitive: if entry A shares an email with B, and B shares one with C, then A, B, and C are all one person. Different people can happen to have the same name, so a name alone never merges anything.
Merge the entries and return one list per person: the name first, followed by every distinct email that person owns, with the emails sorted lexicographically. The merged lists themselves may be returned in any order — the grader prints them in a fixed sorted order.
Example 1:
Input: accounts = [["alice","a@ex.com","b@ex.com"], ["bob","c@ex.com"], ["alice","b@ex.com","d@ex.com"], ["alice","e@ex.com"]]
Output: [["alice","a@ex.com","b@ex.com","d@ex.com"], ["alice","e@ex.com"], ["bob","c@ex.com"]]
Explanation: The first and third entries both contain b@ex.com, so they are the same alice and merge into {a@ex.com, b@ex.com, d@ex.com}. The alice with e@ex.com shares no email with them — a different person who happens to have the same name. Bob stands alone.
Example 2:
Input: accounts = [["dana","x@m.io","y@m.io"], ["dana","y@m.io","z@m.io"], ["dana","z@m.io","w@m.io"]]
Output: [["dana","w@m.io","x@m.io","y@m.io","z@m.io"]]
Explanation: Entry 1 links to entry 2 through y@m.io, and entry 2 links to entry 3 through z@m.io. The chain makes all three one person with four distinct emails.
Constraints:
- 1 ≤ accounts.length ≤ 1000
- 2 ≤ accounts[i].length ≤ 10
- 1 ≤ accounts[i][j].length ≤ 30
- Names consist of lowercase English letters; emails consist of letters, digits, '.' and '@'.
- If two entries share an email they belong to the same person, so their names are identical.
Hints:
Think of every email as a node in a graph. Each account entry connects all of its emails together. Merged accounts are exactly the connected components of that graph.
You don't need edges between every pair of emails in an entry — connecting each email to the entry's first email (a star) is enough to make the component whole.
A Disjoint Set Union (union-find) structure keyed by email string finds the components in near-linear time: union every email with its entry's first email, then group emails by their root.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: accounts = [["alice","a@ex.com","b@ex.com"], ["bob","c@ex.com"], ["alice","b@ex.com","d@ex.com"], ["alice","e@ex.com"]]
Expected output: [["alice","a@ex.com","b@ex.com","d@ex.com"], ["alice","e@ex.com"], ["bob","c@ex.com"]]