codejump
MediumPro challengePythonJavaScriptTypeScript

Graph — Accounts Merge

Data StructuresGraphsUnion FindHash Table

solve(accounts) — accounts[i] = [name, email1, email2, ...]. Two accounts
belong to the same person if they share at least one email, even when the
accounts were created with different spellings of the name field; accounts with the
same name but no shared email are different people.

Merge the accounts. Return a list where each entry is the name followed by that
person's distinct emails in sorted order. Sort the entries themselves by their
first email.

Think of emails as nodes and each account as edges that join its emails: a merged
account is a connected component, found with Union–Find or DFS.

Examples

solve([["John","johnsmith@mail.com","john_newyork@mail.com"],
       ["John","johnsmith@mail.com","john00@mail.com"],
       ["Mary","mary@mail.com"],
       ["John","johnnybravo@mail.com"]])
  → [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
     ["John","johnnybravo@mail.com"],
     ["Mary","mary@mail.com"]]

Sample tests

Test #1Classic example
Input: [[["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["John","johnnybravo@mail.com"],["Mary","mary@mail.com"]]
Test #2Same name, no shared email
Input: [[["A","x@m.com"],["A","y@m.com"]]]
Output: [["A","x@m.com"],["A","y@m.com"]]
Test #3Single account
Input: [[["A","b@m.com"]]]
Output: [["A","b@m.com"]]