721.Accounts_Merge(Medium).md

721. Accounts Merge (Medium)

Date and Time: Dec 20, 2024, 10:48 (EST)

Link: https://leetcode.com/problems/accounts-merge

Question:

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 definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts =
[["John","[email protected]","[email protected]"],
["John","[email protected]","[email protected]"],
["Mary","[email protected]"],
["John","[email protected]"]]

Output:
[["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],
["John","[email protected]"]]

Explanation:
The first and second John's are the same person as they have the common email "[email protected]".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', '[email protected]'], ['John', '[email protected]'],
['John', '[email protected]', '[email protected]', '[email protected]']] would still be accepted.

Example 2:

Input: accounts =
[["Gabe","[email protected]","[email protected]","[email protected]"],
["Kevin","[email protected]","[email protected]","[email protected]"],
["Ethan","[email protected]","[email protected]","[email protected]"],
["Hanzo","[email protected]","[email protected]","[email protected]"],
["Fern","[email protected]","[email protected]","[email protected]"]]

Output:
[["Ethan","[email protected]","[email protected]","[email protected]"],
["Gabe","[email protected]","[email protected]","[email protected]"],
["Hanzo","[email protected]","[email protected]","[email protected]"],
["Kevin","[email protected]","[email protected]","[email protected]"],
["Fern","[email protected]","[email protected]","[email protected]"]]

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.

Walk-through:

Union Find:
We can solve this problem by using Union Find data structure to have disjoint sets.

1. Access accounts to map each email e in each list with their index i, which is the index in accounts. So we have {email: id}, we check if an email already exists in emailAcct{}, if so, we union the existed id with current index, uf.union(i, emailAcct[e]).

2. Then, loop over emailAcct{id: [email]} to group all the emails with the same id together.

3. Use accounts[i][0] to get name, use index i to access idEmails[i] to get all this name's associated emails and sort them and append [name] + sorted(idEmails[i]) into res[].

DFS Solution:
To run DFS, we first buid adjacent list for the first email in each list in accounts with each of the rest emails.

Then, we traverse all the emails again with visited() to add all current email's neighbors into [] for this name.

Union Find Solution:

class UF:
    def __init__(self, size):
        self.root = [i for i in range(size)]    # return each index's root
        self.rank = [1] * size

    # Find x's root from self.root
    def find(self, x):
        # Repeatly update x to be current x's root, then we find x's root's root until x = self.root[x], because the default value of root 0 will be 0 = self.root[x] = 0
        while x != self.root[x]:
            x = self.root[x]
        return x

    # First find the root of x, y, then update the root of x to be y or the root of y to be x base on which rank is higher
    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        # Update root base on rank
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootY] > self.rank[rootX]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # TC: O(nk*log(nk)), n=len(accounts), k=len(accounts[0]), SC: O(n*k)
        uf = UF(len(accounts))
        # Map each email with acctId (index of accounts)
        # Check if an email already in hashmap, if so, union current id and the existed id
        emailAcct = {}    # {email: id}
        for i, acct in enumerate(accounts):
            # Accessing emails
            for e in acct[1:]:
                # Union common email's id
                if e in emailAcct:
                    uf.union(i, emailAcct[e])
                else:
                    emailAcct[e] = i


        # Map the same id with list of emails, find the root (leader) of index i, then append email into hashmap[leader]
        idEmails = collections.defaultdict(list)    # {id: [email]}
        for e, i in emailAcct.items():
            root = uf.find(i)
            idEmails[root].append(e)


        # Put the result into res[] by following the format
        res = []
        for i, emails in idEmails.items():
            name = accounts[i][0]
            res.append([name] + sorted(emails)
        return res

Time Complexity: $O(nk * log(nk))$, uf.find() and uf.union() each takes $O(log\ n)$, sorted() takes $O(klog\ k)$.
Space Complexity: $O(n)$

DFS Solution:

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # TC: O(nlogn), n is total emails, SC: O(n)

        # DFS to append all node's neighbors into tmp[]
        def dfs(node, tmp):
            visited.add(node)
            for nei in adj[node]:
                if nei not in visited:
                    dfs(nei, tmp)
            tmp.append(node)
            return tmp

        # First, connect all the emails together
        # Create adj list, for each acct add an edge between the first email and each of the other emails in the acct
        # Add each email from accounts

        adj = collections.defaultdict(set)
        for acct in accounts:
            # Add edge between the first email with the rest emails
            for e in acct[1:]:
                adj[acct[1]].add(e)
                adj[e].add(acct[1])

        visited = set()
        res = []
        for acct in accounts:
            name = acct[0]
            for e in acct[1:]:
                if e not in visited:
                    res.append([name] + sorted(dfs(e, [])))
        return res

Time Complexity: $O(nlog\ n)$
Space Complexity: $O(n)$