Hand of Straights

Problem

You are given an integer array hand (a hand of cards, each an integer value) and an integer groupSize. Determine whether the cards can be rearranged into groups such that every group has exactly groupSize cards and the values within each group are consecutive integers (e.g. [4,5,6] for groupSize = 3).

Return True if such a partition of all the cards exists, otherwise False. Every card must be used exactly once.

(This is identical to LeetCode’s “Divide Array in Sets of K Consecutive Numbers.”)

Examples

• hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 → True — split into [1,2,3], [2,3,4], [6,7,8].
• hand = [1,2,3,4,5], groupSize = 4 → False — 5 is not divisible by 4, so equal-sized groups are impossible.
• hand = [8,10,12], groupSize = 3 → False — the values are not consecutive, so no run of 3 can be formed.

Constraints

• 1 <= len(hand) <= 10^4
• 0 <= hand[i] <= 10^9
• 1 <= groupSize <= len(hand)

Values can be huge, so index-by-value arrays are out; a hash count keyed on value is the right structure.

Think about it first

TL;DR

Count values, then repeatedly force the smallest remaining value to start a run of groupSize consecutive cards — O(n log n) time, O(n) space.

Approach 1 — Brute force: try to build groups by search

Sort the cards and recursively pick, for the current smallest card, the run it must complete, backtracking on failure. Without the greedy insight this is exponential in the worst case because you might try many ways to pair up duplicates.

from collections import Counter
from typing import List

def isNStraightHand(hand: List[int], groupSize: int) -> bool:
    if len(hand) % groupSize != 0:
        return False
    count = Counter(hand)

    def solve() -> bool:
        if not any(count.values()):
            return True
        start = min(v for v, c in count.items() if c > 0)
        for card in range(start, start + groupSize):
            if count[card] == 0:
                return False
            count[card] -= 1
        return solve()

    return solve()

Complexity: because min fixes the unique starting card, this formulation is already the greedy recursion rather than a true search. A genuine brute force that tries every subset of groupSize cards for each group is exponential, roughly O(2^n), and infeasible at n = 10^4. Once the smallest card is recognized as having no freedom, the search space collapses to a single path.

Approach 2 — Greedy with a min-heap of distinct values

The greedy-choice property (why the smallest card forces its group): Let x be the smallest value with cards remaining. In any valid partition, the group containing x cannot have x in a middle or last slot, because that would require a card smaller than x (namely x-1) to sit before it — and none exists. So x must be the first, smallest element of its group, which fixes that group to exactly [x, x+1, ..., x+groupSize-1]. The decision is forced, so it is also globally optimal. Commit to it, remove those cards, and recurse on the next-smallest value.

A min-heap (or the sorted distinct keys) lets us always fetch the current smallest value cheaply. We consume one of each value in the run; if a needed value is exhausted mid-run, the partition is impossible.

from collections import Counter
from typing import List
import heapq

def isNStraightHand(hand: List[int], groupSize: int) -> bool:
    if len(hand) % groupSize != 0:
        return False
    count = Counter(hand)
    heap = list(count.keys())
    heapq.heapify(heap)
    while heap:
        start = heap[0]                     # current smallest value
        for card in range(start, start + groupSize):
            if count[card] == 0:
                return False                # run is broken
            count[card] -= 1
            if count[card] == 0:
                if card != heap[0]:
                    # a needed value ran out but isn't the current
                    # minimum -> future groups can never use it
                    return False
                heapq.heappop(heap)
    return True

Walkthrough on hand = [1,2,3,6,2,3,4,7,8], groupSize = 3:

1. count = {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}, heap min-orders the distinct keys.
2. start = 1: consume 1,2,3. count = {1:0, 2:1, 3:1, 4:1, 6:1, 7:1, 8:1}. 1 hit zero as the current min → pop it. Group [1,2,3].
3. start = 2: consume 2,3,4. count = {2:0, 3:0, 4:0, 6:1, 7:1, 8:1}. Each hit zero as the running min → popped in turn. Group [2,3,4].
4. start = 6: consume 6,7,8. All hit zero → popped. Group [6,7,8].
5. Heap empty → True.

Complexity: O(n log n) — building the heap is O(d log d) for d distinct values, and each card is consumed once with at most one O(log d) heap pop; the Counter is O(n). Space O(n) for the counter and heap.

Variant: instead of a heap, sort the distinct keys once and iterate, using the count map to skip already-used values. Same O(n log n) cost, and often clearer to read.

Common pitfalls

• Forgetting the len(hand) % groupSize != 0 early reject; the run-building loop can otherwise report a false positive on unbalanced counts.
• Peeking the minimum but not verifying that a value which hits zero is the current minimum. If x+2 runs out while x still has cards, a later group starting at x will need x+2 and can never get it — that must fail now.
• Mutating the heap while consuming a run without keeping counts in sync — always decrement the counter, and only pop when a value reaches zero.

Pattern takeaway

When items must be grouped into consecutive runs, the extreme element (smallest or largest) usually has no freedom — it anchors its group. Greedily place the forced element first, remove its committed run, and repeat; a heap or sorted counter serves the extreme element cheaply each round.