Hand of Straights medium

Problem Statement

You are given an integer array hand representing the hand of cards held by a player and an integer groupSize representing the size of groups of consecutive cards.

Return true if you can divide the cards into groups of size groupSize such that within each group, the cards are consecutive in value. Otherwise, return false.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation:
We can group the cards as [1,2,3], [2,3,4], [6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation:
We cannot find a group of size 4 that is consecutive.

Steps and Explanation

The problem can be solved efficiently using a counter (dictionary) and a greedy approach. Here's the breakdown:

1. Count Card Frequencies: Create a counter (using collections.Counter) to store the frequency of each card in the hand. This allows for quick access to the number of times each card appears.

2. Iterate and Group: Iterate through the unique card values (sorted). For each card:

   • Check if it's already been assigned to a group. If so, continue.
   • Check if there are enough consecutive cards to form a group of size groupSize. This involves checking the frequency of the current card and the groupSize - 1 subsequent cards.
   • If a group can be formed, decrement the counts of all the cards in the group. If at any point the count of a card goes below zero, it means we don't have enough cards to form the group, and we return False.
   • If we successfully create the group, continue to the next unique card.

3. Check for Remaining Cards: After iterating through all unique cards, check if the counter is empty. If it is, all cards have been grouped, and we return True. Otherwise, some cards are left ungrouped, and we return False.

Code

import collections

def isNStraightHand(hand, groupSize):
    """
    Checks if a hand of cards can be divided into groups of consecutive cards.

    Args:
        hand: A list of integers representing the hand of cards.
        groupSize: The size of the groups.

    Returns:
        True if the cards can be grouped, False otherwise.
    """
    if len(hand) % groupSize != 0:
        return False  # Cannot form groups of groupSize

    count = collections.Counter(hand)
    sorted_cards = sorted(count.keys())

    for card in sorted_cards:
        if count[card] == 0:
            continue
        for i in range(card, card + groupSize):
            if count[i] == 0:
                return False  # Not enough consecutive cards
            count[i] -= 1

    return all(c == 0 for c in count.values()) # Check if all cards are used

Complexity

• Time Complexity: O(N log N), where N is the number of cards. This is dominated by the sorting of the keys in the counter (if the input is not already sorted), and the iteration through the cards.
• Space Complexity: O(N) in the worst case to store the counter (dictionary) if all cards are unique. In the best case (many duplicates), space complexity can be less than O(N).