leetcode

// 846. Hand of Straights
#include "leetcode.h"

/*
 * alice has some number of cards and she wants to rearrange the cards into
 * groups so that each group is of size 'groupSize' and consists of 'groupSize'
 * consecutive cards. given an integer array 'hand' where 'hand[i]' is the value
 * written on the i'th card and an integer 'groupSize', return true if she can
 * rearrange the cards or false otherwise.
 */

struct pair {
  int num;
  int cnt;
};

int cmp(const void *a, const void *b) {
  return *(const int *)a - *(const int *)b;
}

bool isNStraightHand(int *hand, int handSize, int groupSize) {
  if (handSize % groupSize)
    return false;
  if (groupSize == 1)
    return true;
  qsort(hand, handSize, sizeof(int), cmp);
  struct pair *arr = (struct pair *)calloc(handSize, sizeof(struct pair));
  arr[0].num = hand[0];
  arr[0].cnt = 1;
  int idx = 0;
  for (int i = 1; i < handSize; i++) {
    if (hand[i] != arr[idx].num)
      idx++;
    arr[idx].num = hand[i];
    arr[idx].cnt++;
  }
  int pos = 0;
  for (int i = 0; i < handSize; i++) {
    while (pos < idx && !arr[pos].cnt)
      pos++;
    if (arr[pos].num == hand[i] && arr[pos].cnt)
      for (int j = 0; j < groupSize; j++) {
        int tar = hand[i] + j;
        if (arr[pos + j].cnt && arr[pos + j].num == tar)
          arr[pos + j].cnt--;
        else {
          free(arr);
          return false;
        }
      }
  }
  free(arr);
  return true;
}

int main() {
  int h1[] = {1, 2, 3, 6, 2, 3, 4, 7, 8}, h2[] = {1, 2, 3, 4, 5};
  printf("%d\n", isNStraightHand(h1, ARRAY_SIZE(h1), 3)); // expect: 1
  printf("%d\n", isNStraightHand(h2, ARRAY_SIZE(h2), 4)); // expect: 0
}