Hand of Straights

Hand of Straights asks whether a hand of cards can be rearranged into groups of W consecutive cards. It is a clean example of a greedy strategy backed by a count map — a pattern that shows up whenever the smallest available item forces your next move.

The slow way first

You could try every possible way to assemble the groups — pick three cards, see if they form a run, recurse on what remains, and backtrack on failure. That explores an exponential number of combinations. It works for tiny hands but blows up fast.

The question to ask: is there one move that is always safe? If so, we never need to backtrack at all.

The idea: always start at the smallest card

There is exactly one safe move. Look at the smallest card still in your hand. Nothing smaller exists to pair with it, so it must be the start of a run. That forces the run to be smallest, smallest+1, ..., smallest+W-1. If any of those consecutive cards is missing, the answer is immediately false.

So: count every card, then repeatedly take the smallest available card and consume W consecutive counts.

A quick early exit: if len(hand) is not divisible by W, no split can possibly work, so return false right away.

Walk through it

Step through the animation. We tally the cards, then start a run at the smallest count that is still positive. The first run starts at 1 and claims 1, 2, 3. With 1 exhausted, the smallest is now 2, claiming 2, 3, 4. Finally 6 starts the run 6, 7, 8. Every count hits zero, so the hand splits cleanly.

Pseudocode

if len(hand) is not divisible by W:
    return false
count = how many of each card we hold
for each distinct card "first" in increasing order:
    if count[first] > 0:
        need = count[first]                 # this many runs must start here
        for card in first .. first + W - 1:
            if count[card] < need:
                return false                # a consecutive card is missing
            count[card] -= need
return true

The Python solution

def is_n_straight_hand(hand, W):
    if len(hand) % W != 0:
        return False
    count = Counter(hand)
    for first in sorted(count):
        if count[first] > 0:
            need = count[first]
            for card in range(first, first + W):
                if count[card] < need:
                    return False
                count[card] -= need
    return True

• The length check on line 2 is a fast reject: an indivisible hand can never split evenly.
• Counter(hand) builds the multiset of remaining cards.
• We scan distinct cards in sorted order, so we always handle the smallest available card first.
• need = count[first] is how many runs must begin at this card — every copy of the smallest card must start its own run.
• The inner loop claims need copies of each of the W consecutive cards; if any is short, we return False.
• If we never fail, every card was placed and we return True.

Complexity

Sorting the distinct cards costs O(n log n); each card is consumed a constant number of times across all runs, giving the n*W term. The count map uses O(n) extra space.

When this pattern shows up

Practice