Hand of Straights medium

Problem Statement

You are given an integer array hand containing integers representing the values of cards in a hand. You are also given an integer groupSize. You want to arrange the cards into groups of groupSize, where each group contains consecutive cards. Consecutive cards have values that differ by exactly 1. Each card must belong to exactly one group. Return true if it is possible to arrange the cards into groups, otherwise return false.

Example 1

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: We can form the following groups: [1,2,3], [2,3,4], [6,7,8].

Example 2

Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: We can't group the cards into groups of size 4.

Steps

1. Sort the hand: Sorting allows us to efficiently check for consecutive numbers.
2. Create a frequency map: Use a map to store the frequency of each card value. This makes it easier to track the availability of cards.
3. Iterate through the sorted hand: For each card, check if there are enough consecutive cards available to form a group.
4. Decrement frequencies: If a group can be formed, decrement the frequencies of the cards in the group.
5. Check for remaining cards: After processing all cards, if the frequency map is empty, it means all cards have been grouped successfully.

Explanation

The solution relies on the greedy approach. We process the cards in sorted order. For each card, we try to form a group starting with that card. If we can't form a group (because we don't have enough consecutive cards), we immediately know it's not possible to arrange all cards into groups, and we return false. The frequency map is crucial for efficient tracking of card availability.

Code

function isNStraightHand(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) return false; // Check for divisibility

    hand.sort((a, b) => a - b); // Sort the hand
    const freqMap = new Map<number, number>();

    // Create frequency map
    for (const card of hand) {
        freqMap.set(card, (freqMap.get(card) || 0) + 1);
    }

    for (const card of hand) {
        if (!freqMap.has(card) || freqMap.get(card) === 0) continue; //Skip already processed cards

        for (let i = 0; i < groupSize; i++) {
            const nextCard = card + i;
            if (!freqMap.has(nextCard) || freqMap.get(nextCard) === 0) {
                return false; //Not enough consecutive cards
            }
            freqMap.set(nextCard, freqMap.get(nextCard)! - 1);
        }
    }

    return true; // All cards grouped successfully
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step (where N is the number of cards). The frequency map operations are O(N) on average.
• Space Complexity: O(N) in the worst case, to store the frequency map. The space used by the sorted array is also O(N).