Hand of Straights (LeetCode 846)

The problem

You hold a hand of cards, each with an integer value, and a number groupSize. Decide whether you can split the whole hand into groups of exactly groupSize cards, where each group is a run of consecutive values (like 3, 4, 5). Every card must be used exactly once.

Input:  hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
Output: True

The groups [1, 2, 3], [2, 3, 4] and [6, 7, 8] use every card.

How to think about it

Start with brute force. Try every way of forming groups with backtracking: pick a card, try to build a run from it, recurse on the rest. The branching is huge and it is exponential in the worst case.

The key insight: the smallest card has no choice. Look at the smallest value x still in the hand. It can’t be the middle or end of a run, because there is nothing smaller to come before it. So it must start a run x, x+1, ..., x+groupSize-1. There is no decision to make, which is exactly when greedy is safe. And if x appears need times, you need need copies of each of the next groupSize - 1 values too.

Process values in sorted order with a counter. Count each value. Walk the distinct values in increasing order. Skip a value whose count has already dropped to 0. Otherwise it is the current smallest, so take its count need and subtract need from each value in its run. If any of those values has fewer than need copies, the hand can’t be split.

Which pattern is this? Greedy with sorting and a hash map. The tell is “split everything into consecutive groups”: the smallest element is forced, so handle it first.

Approach

1. If the hand size isn’t a multiple of groupSize, return False straight away.
2. Count how many times each value appears.
3. Go through the distinct values in sorted order.
4. For a value x with a positive count need, check each value from x to x + groupSize - 1. If any has a count below need, return False. Otherwise subtract need from it.
5. If every value is handled, return True.

Solution

from collections import Counter
def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size:
        return False
    cnt = Counter(hand)
    for x in sorted(cnt):
        if cnt[x] > 0:                       # x is the smallest card left: it must start runs
            need = cnt[x]
            for k in range(x, x + group_size):
                if cnt[k] < need:            # not enough copies to complete every run
                    return False
                cnt[k] -= need
    return True
# is_n_straight_hand([1,2,3,6,2,3,4,7,8], 3) -> True

Dry run

The counts start as {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}.

No run ran short, so the answer is True.

Complexity

• Time: O(n log n). Sorting the distinct values dominates. Each run start consumes at least groupSize cards, so there are at most n / groupSize starts, each doing groupSize work: O(n) in total.
• Space: O(n). The counter holds up to n distinct values.

Edge cases and pitfalls

• Hand size not divisible by groupSize fails immediately.
• groupSize = 1 is always True: every card is its own run.
• Gaps like [1, 2, 4] with size 3: cnt[3] is 0, so it returns False. Counter returns 0 for missing keys instead of raising.
• Subtracting one at a time with a heap also works, but handling all need copies at once is simpler and faster.
• Starting runs at an arbitrary card instead of the smallest breaks the “no choice” argument.

Related problems

• Longest Consecutive Sequence (LeetCode 128): also finds where runs start, using a set.
• Assign Cookies (LeetCode 455): sort, then always deal with the smallest item first.
• Merge Triplets to Form Target Triplet (LeetCode 1899): another greedy where each element is either forced or harmless.