846. Hand of Straights

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.
 

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice’s hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice’s hand can not be rearranged into groups of 4.

Constraints:

• $1<=hand.length<=10^4$
• $0<=hand[i]<=10^9$
• 1 <= groupSize <= hand.length

From: LeetCode
Link: 846. Hand of Straights

Solution:

Ideas:

• Sort the hand.

• Compress into (value, count) pairs.

• Scan left to right: if cnt[i] = c > 0, you must open c groups starting at vals[i]. Deduct c from counts of vals[i]…vals[i]+groupSize-1.

• If any required value is missing or under-counted, return false; otherwise succeed.

Code:

static int cmp_int(const void *a, const void *b) {
    int x = *(const int*)a, y = *(const int*)b;
    return (x > y) - (x < y);
}

bool isNStraightHand(int* hand, int handSize, int groupSize) {
    if (groupSize == 1) return true;
    if (handSize % groupSize != 0) return false;

    qsort(hand, handSize, sizeof(int), cmp_int);

    // Run-length encode the sorted hand into unique values and their counts
    int *vals = (int*)malloc(sizeof(int) * handSize);
    int *cnt  = (int*)malloc(sizeof(int) * handSize);
    if (!vals || !cnt) { free(vals); free(cnt); return false; }

    int u = 0;
    for (int i = 0; i < handSize; ) {
        int v = hand[i];
        int j = i;
        while (j < handSize && hand[j] == v) j++;
        vals[u] = v;
        cnt[u]  = j - i;
        u++;
        i = j;
    }

    // Greedily form sequences starting from the smallest available value
    for (int i = 0; i < u; ++i) {
        int c = cnt[i];
        if (c == 0) continue;  // nothing to start at this value
        // Need to consume 'c' copies of vals[i], vals[i]+1, ..., vals[i]+groupSize-1
        for (int off = 0; off < groupSize; ++off) {
            int j = i + off;
            if (j >= u || vals[j] != vals[i] + off) {
                free(vals); free(cnt);
                return false; // missing a required consecutive value
            }
            if (cnt[j] < c) {
                free(vals); free(cnt);
                return false; // not enough cards of this value
            }
            cnt[j] -= c;
        }
    }

    free(vals); free(cnt);
    return true;
}