Loading problem…

289. Accounts Merge

MediumGraph

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts belong to the same person if there is some common email existing in both accounts. Return the accounts in the merged format. The accounts can be returned in any order, and the emails must be sorted.

Examples

Example 1

Input: accounts = [["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"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Explanation: The first and second accounts share johnsmith@mail.com, so they belong to the same John and are merged with their emails sorted. The third John shares no email with them, so he stays a separate person, and Mary is on her own.

Example 2

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]

Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Explanation: No email appears in more than one account, so nothing is merged. Each account is returned as-is with its emails sorted.

Example 3

Input: accounts = [["A","a@b.com"]]

Output: [["A","a@b.com"]]

Explanation: There is only one account, so it is returned unchanged.

Constraints

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] consists of English letters.
accounts[i][j] (for j > 0) is a valid email.

How to solve Accounts Merge: approach and complexity

Union Find: O(n*k*alpha(n)) time, O(n*k) space.

Map each email to an account index. If the same email appears in two accounts, union them. Then group emails by their root account.

Watch it run step by step