aboutsummaryrefslogtreecommitdiff
path: root/accounts_merge.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-18 21:12:37 -0600
committerJack Sangdahl <[email protected]>2024-08-18 21:12:37 -0600
commit1d40fa67f4c59b46b14637f2b339f48f69c57df4 (patch)
treee28574970680352e69f73bc5fa87c7b12648706f /accounts_merge.py
parentc7e6fe204a088a556f0022cbc56fbf5c6839749f (diff)
downloadleetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.tar.gz
leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.zip
721. accounts merge
Diffstat (limited to 'accounts_merge.py')
-rw-r--r--accounts_merge.py73
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=[
+ ["Mary", "[email protected]"],
+ ["John", "[email protected]"],
+ ]
+ )
+ )
+ print(
+ obj.accountsMerge(
+ accounts=[
+ ]
+ )
+ )