846. Hand of Straights

Description

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⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Solutions

Solution 1: Hash Table + Sorting

We first check whether the length of the array \(\textit{hand}\) is divisible by \(\textit{groupSize}\). If it is not, this means that the array cannot be partitioned into multiple subarrays of length \(\textit{groupSize}\), so we return \(\text{false}\).

Next, we use a hash table \(\textit{cnt}\) to count the occurrences of each number in the array \(\textit{hand}\), and then we sort the array \(\textit{hand}\).

After that, we iterate over the sorted array \(\textit{hand}\). For each number \(x\), if \(\textit{cnt}[x] \neq 0\), we enumerate every number \(y\) from \(x\) to \(x + \textit{groupSize} - 1\). If \(\textit{cnt}[y] = 0\), it means that we cannot partition the array into multiple subarrays of length \(\textit{groupSize}\), so we return \(\text{false}\). Otherwise, we decrement \(\textit{cnt}[y]\) by \(1\).

If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return \(\text{true}\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{hand}\).

Python3JavaC++GoTypeScript

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        cnt = Counter(hand)
        for x in sorted(hand):
            if cnt[x]:
                for y in range(x, x + groupSize):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        Arrays.sort(hand);
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : hand) {
            cnt.merge(x, 1, Integer::sum);
        }
        for (int x : hand) {
            if (cnt.getOrDefault(x, 0) > 0) {
                for (int y = x; y < x + groupSize; ++y) {
                    if (cnt.merge(y, -1, Integer::sum) < 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize) {
            return false;
        }
        ranges::sort(hand);
        unordered_map<int, int> cnt;
        for (int x : hand) {
            ++cnt[x];
        }
        for (int x : hand) {
            if (cnt.contains(x)) {
                for (int y = x; y < x + groupSize; ++y) {
                    if (!cnt.contains(y)) {
                        return false;
                    }
                    if (--cnt[y] == 0) {
                        cnt.erase(y);
                    }
                }
            }
        }
        return true;
    }
};

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 {
        return false
    }
    sort.Ints(hand)
    cnt := map[int]int{}
    for _, x := range hand {
        cnt[x]++
    }
    for _, x := range hand {
        if cnt[x] > 0 {
            for y := x; y < x+groupSize; y++ {
                if cnt[y] == 0 {
                    return false
                }
                cnt[y]--
            }
        }
    }
    return true
}

function isNStraightHand(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) {
        return false;
    }
    const cnt = new Map<number, number>();
    for (const x of hand) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    hand.sort((a, b) => a - b);
    for (const x of hand) {
        if (cnt.get(x)! > 0) {
            for (let y = x; y < x + groupSize; y++) {
                if ((cnt.get(y) || 0) === 0) {
                    return false;
                }
                cnt.set(y, cnt.get(y)! - 1);
            }
        }
    }
    return true;
}

Solution 2: Ordered Set

Similar to Solution 1, we first check whether the length of the array \(\textit{hand}\) is divisible by \(\textit{groupSize}\). If it is not, this means that the array cannot be partitioned into multiple subarrays of length \(\textit{groupSize}\), so we return \(\text{false}\).

Next, we use an ordered set \(\textit{sd}\) to count the occurrences of each number in the array \(\textit{hand}\).

Then, we repeatedly take the smallest value \(x\) from the ordered set and enumerate each number \(y\) from \(x\) to \(x + \textit{groupSize} - 1\). If all these numbers appear at least once in the ordered set, we decrement their occurrence count by \(1\). If any count reaches \(0\), we remove that number from the ordered set. Otherwise, if we encounter a number that does not exist in the ordered set, it means that the array cannot be partitioned into valid subarrays, so we return \(\text{false}\). If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return \(\text{true}\).