Hand of Straights

Given an integer array hand and an integer groupSize, determine whether you can rearrange all cards into groups of size groupSize where each group consists of consecutively increasing values (each step = 1). Return true if possible, false otherwise.

• 1 ≤ hand.length ≤ 1000
• 0 ≤ hand[i] ≤ 1000
• 1 ≤ groupSize ≤ hand.length

Examples

How to think about it

The key greedy insight: always form the group starting from the smallest available card. Why? Because the smallest card can only start a group — it can never be the 2nd, 3rd, or later card in any group (those require something smaller). If we delay using the smallest card, we'll eventually run out of cards to pair it with.

So the algorithm is:

1. Check divisibility — len(hand) % groupSize ≠ 0 → immediately false.
2. Build a frequency map to track how many of each card remain.
3. Sort and iterate. For each card value num that still has cards available, try to form a group [num, num+1, ..., num+groupSize-1].
4. If any required card in that window is missing → false.
5. Otherwise decrement counts for all cards in the group and continue.

All Approaches

1. Sorting + Frequency Map — O(n log n)

Sort the hand so we always encounter the smallest available card first. Use a Counter to track remaining counts. For each card in sorted order, if its count is still positive, try to consume a full group starting there.

def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize:
        return False

    count = Counter(hand)
    hand.sort()

    for num in hand:
        if count[num]:                         # still has cards at this value
            for i in range(num, num + groupSize):
                if not count[i]:
                    return False
                count[i] -= 1
    return True

2. Min-Heap — O(n log n)

Instead of sorting the original array, maintain a min-heap of distinct card values. At each step, the heap top gives the smallest remaining value. Form a group from it, decrementing counts. When a count hits zero, it must be the heap's current minimum — pop it. If it isn't the minimum, some smaller value is stranded and we return false.

def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize:
        return False

    count = {}
    for n in hand:
        count[n] = 1 + count.get(n, 0)

    minH = list(count.keys())
    heapq.heapify(minH)

    while minH:
        first = minH[0]
        for i in range(first, first + groupSize):
            if i not in count:
                return False
            count[i] -= 1
            if count[i] == 0:
                if i != minH[0]:   # can't remove mid-heap safely
                    return False
                heapq.heappop(minH)
    return True

3. Ordered Map + Queue — O(n log n)

Track how many groups are currently open (started but not yet complete). Process values in sorted order. At each value num:

• If there are open groups waiting for num but num isn't consecutive to the previous value → impossible.
• If count[num] < open_groups → not enough cards to extend all open groups → impossible.
• The surplus (count[num] - open_groups) starts new groups.
• A queue tracks how many groups started at each value. When the queue length reaches groupSize, those groups close — subtract their count from open_groups.

def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize != 0:
        return False

    count = Counter(hand)
    q = deque()
    last_num, open_groups = -1, 0

    for num in sorted(count):
        if (open_groups > 0 and num > last_num + 1) or open_groups > count[num]:
            return False

        q.append(count[num] - open_groups)
        last_num    = num
        open_groups = count[num]

        if len(q) == groupSize:
            open_groups -= q.popleft()

    return open_groups == 0

Pattern: Greedy Grouping

This problem is the template for a class of problems where you must partition elements into valid groups. The pattern works when:

• There is a natural ordering to elements (here: numeric order).
• The smallest unplaced element has a unique forced role — it can only belong to one kind of group (the one it starts).
• Forming that group greedily at each step is provably optimal.

Same idea in disguise

• 2406. Divide Intervals Into Minimum Number of Groups — sort intervals, greedily assign to existing groups.
• 1296. Divide Array in Sets of K Consecutive Numbers — identical problem, different variable name (k instead of groupSize).
• 659. Split Array into Consecutive Subsequences — each existing open subsequence can be extended, otherwise start a new one. Same queue/open-groups logic.

Why the heap check if i != minH[0]: return False works

When count[i] drops to zero, card value i is exhausted. If i is not currently the heap minimum, there exists some smaller value j < i that still has cards — but no group can extend to include j anymore (all groups passing through j would need to have also included j-1, j-2, etc.). That smaller value is now stranded. Returning false immediately is correct.

Where people go wrong

Forgetting the divisibility check

If len(hand) % groupSize ≠ 0, you can't form complete groups — return false immediately. Without this, the loop may silently "succeed" on an invalid input.

Not starting groups from the smallest available card

If you start a group from an arbitrary card, you might leave smaller cards stranded. The sort (or heap) enforces that the smallest unplaced card is always processed first.

Using a regular dict instead of sorted iteration

In Python, Counter doesn't iterate in sorted order. Iterating over hand (after sorting) or sorted(count) is required. Using count.keys() directly gives arbitrary order in older Python versions.

Quick tests

• hand=[1], groupSize=1 → true (single card is its own group)
• hand=[1,2,3], groupSize=2 → false (3 cards, groupSize=2: 3%2≠0)
• hand=[1,1,2,2,3,3], groupSize=3 → true: [1,2,3] and [1,2,3]
• hand=[1,2,3,4,5,6], groupSize=3 → true: [1,2,3] and [4,5,6] — but also could be [1,2,3],[2,3,4],[...]. Greedy picks [1,2,3],[4,5,6]. ✓

What to do next

• Gas StationMediumGreedy skip — smallest-first reasoning applied to a circular route.›
• 659. Split Array into Consecutive SubseqsMediumSame open-groups queue idea — can you extend an existing run or must you start a new one?›
• 1296. Divide Array in Sets of KMediumIdentical problem, different variable name — recognize the pattern instantly.›
• Jump GameMediumGreedy — smallest-first / furthest-reach reasoning.›