Hand of Straights — LeetCode

[Prapattimynk]

Task: Hand of Straights
Difficulty: Medium

Alice has some 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 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:
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]

Algorithm:
[olist=1]
[*]Check if the length of the hand array is divisible by groupSize. If not, return false.
[*]Create a cardCount map to store the count of each card in the hand array.
[*]Iterate over the hand array and update the cardCount map. Then iterate again to create groups:
- Find the starting card startCard for a potential sequence by decreasing startCard until you find a card missing in the cardCount map.
- Try to form a sequence of groupSize cards starting from startCard. If any card is missing, return false.
- If the sequence can be formed, decrease the count of each card in that sequence in the cardCount map.
[/olist]

Solution (C++):

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }

        unordered_map<int, int> cardCount;
        for (int card : hand) {
            cardCount[card]++;
        }

        sort(hand.begin(), hand.end());

        for (int card : hand) {
            if (cardCount[card] == 0) {
                continue;
            }

            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }

        return true;
    }
};

Knowledge Base:
This problem is a classic application of Greedy + Hash Map technique. Sorting ensures that we always form groups starting from the smallest card available, avoiding sequence breaks.

Extra Tip:
- Time Complexity: O(n log n) due to sorting.
- Space Complexity: O for storing counts.
- You can optimize by using map instead of unordered_map to automatically get sorted keys without an explicit sort step.