aboutsummaryrefslogtreecommitdiff
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
parentc7e6fe204a088a556f0022cbc56fbf5c6839749f (diff)
downloadleetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.tar.gz
leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.zip
721. accounts merge
-rw-r--r--accounts_merge.c181
-rw-r--r--accounts_merge.py73
2 files changed, 254 insertions, 0 deletions
diff --git a/accounts_merge.c b/accounts_merge.c
new file mode 100644
index 0000000..05c49f5
--- /dev/null
+++ b/accounts_merge.c
@@ -0,0 +1,181 @@
+// 721. Accounts Merge
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int cmp(const void *a, const void *b) {
+ char *a1 = *(char **)a, *b1 = *(char **)b;
+ return strcmp(a1, b1);
+}
+
+int find(int *parent, int i) {
+ if (parent[i] == i)
+ return i;
+ else
+ return parent[i] = find(parent, parent[i]);
+}
+
+void _union(int *parent, int *rank, int i, int j) {
+ i = find(parent, i);
+ j = find(parent, j);
+ if (i == j)
+ return;
+ if (rank[i] > rank[j])
+ parent[j] = i;
+ else {
+ parent[i] = j;
+ if (rank[i] == rank[j])
+ rank[j]++;
+ }
+}
+
+int get_idx(const char *email, const char **emails, int emails_size) {
+ const char **val = bsearch(&email, emails, emails_size, sizeof(char *), cmp);
+ return (int)(val - emails);
+}
+
+struct res_data {
+ char ***r;
+ int *cols;
+ int size;
+ int cap;
+ char **curr;
+ int curr_size;
+ int curr_cap;
+};
+
+void add(struct res_data *r, char *val) {
+ if (r->curr_cap <= r->curr_size) {
+ r->curr_cap = (r->curr_cap + 1) * 2;
+ r->curr = (char **)realloc(r->curr, r->curr_cap * sizeof(char *));
+ }
+ r->curr[r->curr_size++] = val;
+}
+
+void flush(struct res_data *r) {
+ if (r->cap <= r->size) {
+ r->cap = (r->cap + 1) * 2;
+ r->r = (char ***)realloc(r->r, r->cap * sizeof(char **));
+ r->cols = (int *)realloc(r->cols, r->cap * sizeof(int));
+ }
+ r->cols[r->size] = r->curr_size;
+ r->r[r->size++] = r->curr;
+ r->curr = NULL;
+ r->curr_cap = r->curr_size = 0;
+}
+
+struct pair {
+ int idx;
+ int grp;
+};
+
+int cmp2(const void *a, const void *b) {
+ const struct pair *p1 = a, *p2 = b;
+ if (p1->grp == p2->grp)
+ return p1->idx - p2->idx;
+ return p1->grp - p2->grp;
+}
+
+char ***accountsMerge(char ***accounts, int accountsSize, int *accountsColSize,
+ int *returnSize, int **returnColumnSizes) {
+ int emails_size, union_find_size, i, j, k, *parent, *rank;
+ char **emails;
+ struct pair *p;
+ struct res_data *r;
+ memset(&r, 0, sizeof(r));
+ for (emails_size = 0, i = 0; i < accountsSize; i++)
+ for (j = 1; j < accountsColSize[i]; j++)
+ emails_size++;
+ emails = (char **)malloc(emails_size * sizeof(char *));
+ for (k = 0, i = 0; i < accountsSize; i++)
+ for (j = 1; j < accountsColSize[i]; j++)
+ emails[k++] = accounts[i][j];
+ qsort(emails, emails_size, sizeof(char *), cmp);
+ for (i = 0; i < emails_size; ++i)
+ if (!j || strcmp(emails[j - 1], emails[i]))
+ emails[j++] = emails[i];
+ emails_size = j;
+ union_find_size = accountsSize + emails_size;
+ parent = (int *)malloc(union_find_size * sizeof(int));
+ rank = (int *)malloc(union_find_size * sizeof(int));
+ p = (struct pair *)malloc(union_find_size * sizeof(struct pair));
+ for (i = 0; i < union_find_size; i++) {
+ parent[i] = i;
+ rank[i] = 0;
+ }
+ for (i = 0; i < accountsSize; i++)
+ for (j = 1; j < accountsColSize[i]; j++) {
+ // int idx = accountsSize + get_idx(accounts[i][j], (int**)emails,
+ // emails_size);
+ int idx = accountsSize +
+ get_idx(accounts[i][j], (const char **)emails, emails_size);
+ _union(parent, rank, i, idx);
+ }
+ for (i = 0; i < union_find_size; i++) {
+ struct pair curr = {i, find(parent, i)};
+ p[i] = curr;
+ }
+ qsort(p, union_find_size, sizeof(struct pair), cmp2);
+ add(r, accounts[p[0].idx][0]);
+ for (i = 1; i < union_find_size; i++)
+ if (p[i].grp != p[i - 1].grp) {
+ flush(r);
+ add(r, accounts[p[i].idx][0]);
+ } else {
+ int idx = p[i].idx - accountsSize;
+ if (idx >= 0)
+ add(r, emails[idx]);
+ }
+ flush(r);
+ *returnSize = r->size;
+ *returnColumnSizes = r->cols;
+ free(p), free(parent), free(rank), free(emails);
+ return r->r;
+}
+
+int main() {
+ int accountsSize = 4, accountsColSize[] = {3, 3, 2, 2}, returnSize,
+ *returnColumnSizes;
+ char ***accounts = malloc(accountsSize * sizeof(char **));
+ accounts[0] = malloc(accountsColSize[0] * sizeof(char *));
+ accounts[0][0] = "John";
+ accounts[0][1] = "[email protected]";
+ accounts[0][2] = "[email protected]";
+ accounts[1] = malloc(accountsColSize[1] * sizeof(char *));
+ accounts[1][0] = "John";
+ accounts[1][1] = "[email protected]";
+ accounts[1][2] = "[email protected]";
+ accounts[2] = malloc(accountsColSize[2] * sizeof(char *));
+ accounts[2][0] = "Mary";
+ accounts[2][1] = "[email protected]";
+ accounts[3] = malloc(accountsColSize[3] * sizeof(char *));
+ accounts[3][0] = "John";
+ accounts[3][1] = "[email protected]";
+ char ***am1 = accountsMerge(accounts, accountsSize, accountsColSize,
+ &returnSize, &returnColumnSizes);
+ for (int i = 0; i < returnSize; i++)
+ for (int j = 0; j < returnColumnSizes[i]; j++) {
+ printf("\"%s\"", am1[i][j]);
+ if (j < returnColumnSizes[i] - 1)
+ printf(", ");
+ }
+ for (int i = 0; i < returnSize; i++)
+ free(am1[i]);
+ free(am1);
+ free(returnColumnSizes);
+ for (int i = 0; i < accountsSize; i++)
+ free(accounts[i]);
+ free(accounts);
+}
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=[
+ ]
+ )
+ )