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

class Solution:
    def isNStraightHand(self, 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: this particular formulation is actually already the greedy recursion (min forces the unique starting card), so it is efficient — but a true brute force that tries every subset of groupSize cards for each group is O(2^n)-ish and hopeless at n = 10^4. The lesson: once you realize the smallest card has no freedom, the search collapses.

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]. There is no alternative to consider: the local decision “give x the smallest consecutive run” is forced, hence trivially 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

class Solution:
    def isNStraightHand(self, 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 worth knowing: instead of a heap you can sort the distinct keys once and iterate, using the count map to skip already-used values — same O(n log n) cost, and some prefer it for clarity.

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.