diff options
author | Jack Sangdahl <[email protected]> | 2024-08-18 21:12:37 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-18 21:12:37 -0600 |
commit | 1d40fa67f4c59b46b14637f2b339f48f69c57df4 (patch) | |
tree | e28574970680352e69f73bc5fa87c7b12648706f /accounts_merge.py | |
parent | c7e6fe204a088a556f0022cbc56fbf5c6839749f (diff) | |
download | leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.tar.gz leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.zip |
721. accounts merge
Diffstat (limited to 'accounts_merge.py')
-rw-r--r-- | accounts_merge.py | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/accounts_merge.py b/accounts_merge.py new file mode 100644 index 0000000..b2fddb5 --- /dev/null +++ b/accounts_merge.py @@ -0,0 +1,73 @@ +# 721. Accounts Merge +from collections import defaultdict + +""" +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 bbelong to the same person +if there is some common email to bboth 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 numbber 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 accout is the name, and the rest of the elements are emails in sorted +order. the accounts themselves can e returned in any order. +""" + + +class union_find: + def __init__(self, n): + self.parents = list(range(n)) + + def union(self, child, parent): + self.parents[self.find(child)] = self.find(parent) + + def find(self, x): + if x != self.parents[x]: + self.parents[x] = self.find(self.parents[x]) + return self.parents[x] + + +class Solution(object): + def accountsMerge(self, accounts): + """ + :type accounts: List[List[str]] + :rtype: List[List[str]] + """ + uf = union_find(len(accounts)) + ownership = {} + for i, (_, *emails) in enumerate(accounts): + for email in emails: + if email in ownership: + uf.union(i, ownership[email]) + ownership[email] = i + ans = defaultdict(list) + for email, owner in ownership.items(): + ans[uf.find(owner)].append(email) + return [[accounts[i][0]] + sorted(emails) for i, emails in ans.items()] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.accountsMerge( + accounts=[ + ["John", "[email protected]", "[email protected]"], + ["John", "[email protected]", "[email protected]"], + ["Mary", "[email protected]"], + ["John", "[email protected]"], + ] + ) + ) + print( + obj.accountsMerge( + accounts=[ + ] + ) + ) |