leetcode

// 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] = "johnsmith@mail.com";
  accounts[0][2] = "john_newyork@mail.com";
  accounts[1] = malloc(accountsColSize[1] * sizeof(char *));
  accounts[1][0] = "John";
  accounts[1][1] = "johnsmith@mail.com";
  accounts[1][2] = "john00@mail.com";
  accounts[2] = malloc(accountsColSize[2] * sizeof(char *));
  accounts[2][0] = "Mary";
  accounts[2][1] = "mary@mail.com";
  accounts[3] = malloc(accountsColSize[3] * sizeof(char *));
  accounts[3][0] = "John";
  accounts[3][1] = "johnnybravo@mail.com";
  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);
}