Hand of Straights

Problem

Problem

You are given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize.

You want to rearrange the cards into groups so that each group is of size groupSize, and card values are consecutively increasing by 1.

Return true if it’s possible to rearrange the cards in this way, otherwise, return false.

Examples

Example 1:

Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4

Output: true

Explanation: The cards can be rearranged as [1,2,3,4] and [2,3,4,5].

Example 2:

Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4

Output: false

Explanation: The closest we can get is [1,2,3,4] and [3,5,6,7], but the cards in the second group are not consecutive.

Constraints

• 1 <= hand.length <= 1000
• 0 <= hand[i] <= 1000
• 1 <= groupSize <= hand.length

You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.

Solution

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) { return false; }
        std::ranges::sort(hand);
        std::unordered_set<int> selected_cards;
 
        // Loop over number of hands to make
        for (int i = 0; i < hand.size() / groupSize; ++i) {
            int curr_hand_size = 0;
            int prev_card = -1;
            // Greedily select next card
            for (int j = 0; j < hand.size(); ++j) {
                if (selected_cards.contains(j)) { continue; }
                if (curr_hand_size == 0 || hand[j] == prev_card + 1 ) {
                    ++curr_hand_size;
                    prev_card = hand[j];
                    selected_cards.insert(j);
                }
                if (curr_hand_size == groupSize) { break; }
            }
            // Was unable to make a groupSize hand
            if (curr_hand_size != groupSize) { return false; }
        }
        return true;
    }
};