Hand of Straights

The smallest remaining card leaves you no freedom: it must begin a run.

Consume a sorted multiset

Sort all cards. Repeatedly take the smallest remaining value, search for every next value needed by its group, and remove each match. A multiset is a collection that keeps duplicate values, so removing one copy never erases the others.

def is_n_straight_hand(hand: list[int], group_size: int) -> bool:
    if len(hand) % group_size != 0:
        return False
 
    cards = sorted(hand)
    while cards:
        start = cards[0]
        for card in range(start, start + group_size):
            try:
                index = cards.index(card)
            except ValueError:
                return False
            cards.pop(index)
    return True

Time O(n²) — repeated linear searches and removals dominate. Space O(n) for the sorted copy.

Smallest-card frequency sweep

Replace physical removals with a frequency map. Visit distinct values in sorted order. If the current smallest value has copies cards left, all copies must begin groups, so subtract that amount from every value in the required run. A shortage makes the hand impossible immediately.

from collections import Counter
 
 
def is_n_straight_hand(hand: list[int], group_size: int) -> bool:
    if len(hand) % group_size != 0:
        return False
 
    counts = Counter(hand)
    for start in sorted(counts):
        copies = counts[start]
        if copies == 0:
            continue
        for card in range(start, start + group_size):
            if counts[card] < copies:
                return False
            counts[card] -= copies
    return True

The exchange argument is a proof that replacing another arrangement with the greedy choice can't destroy a solution. Let x be the smallest remaining card. In any valid arrangement, x can't sit after another card in its group: that predecessor would be smaller than x, but no smaller card remains. So every valid arrangement must start a group at x. Exchange whichever group contains x for the forced run x, x + 1, ..., x + groupSize - 1; it uses exactly the cards every solution must reserve for that start. Repeating the forced exchange makes the smallest-first choice globally optimal. Missing any required successor proves no arrangement exists.

Time O(n log n) — sorting the distinct values dominates; frequency consumption is linear in the cards removed. Space O(n) for the counts and sorted keys.