Hand of Straights · DSA Prep

This problem is the same as 1296. Divide Array in Sets of K Consecutive Numbers.

Brute Force: Repeated Extraction

Time O(n²)Space O(n)

Count how many of each card value there are. Repeatedly find the smallest value that still has copies left, and try to peel off one full run of groupSize consecutive values starting there. If any required value is missing, fail immediately.

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        count = Counter(hand)
        remaining = len(hand)
        while remaining > 0:
            start = min(v for v in count if count[v] > 0)
            for v in range(start, start + groupSize):
                if count[v] <= 0:
                    return False
                count[v] -= 1
            remaining -= groupSize
        return True

Finding the current minimum by scanning the counter is O(n), and it repeats roughly n / groupSize times, so this is O(n²) in the worst case.

Greedy: Sorted Keys, Consume Whole Runs

OptimalTime O(n log n)Space O(n)

The key realization: whatever the smallest remaining card value is, it must be the start of some group — no card smaller than it exists to precede it in a run of consecutive values. So instead of repeatedly re-scanning for the minimum, sort the distinct values once. Walk them in order; whenever a value still has need = count[value] copies left, that many groups must all start at value right now — consume need copies from each of value, value+1, ..., value+groupSize-1 all at once (failing if any of them doesn’t have enough).

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        count = Counter(hand)
        for start in sorted(count):
            need = count[start]
            if need <= 0:
                continue
            for v in range(start, start + groupSize):
                if count[v] < need:
                    return False
                count[v] -= need
        return True

Play the walk over the sorted-key ledger below — the trace is generated by replaying the code itself, so the chips can never disagree with it. Watch why the smallest remaining card is always forced to start a group, and how leftover copies carry into the next group:

hand[1, 2, 3, 6, 2, 3, 4, 7, 8]groupSize3

Sorted distinct values — remaining copies

·11

·22

·32

·41

·61

·71

·81

groups locked innone yet

1 / 12

group start (smallest remaining)consumed into the groupneed check (count 0)missing card / strandedused up

Sort the distinct values once and count copies: 1 x1, 2 x2, 3 x2, 4 x1, 6 x1, 7 x1, 8 x1, groupSize = 3. The rule to watch: the smallest remaining card has nothing smaller to precede it in a run, so it has no choice but to start a group.

All nine cards land in three groups of three consecutive values — [1,2,3], [2,3,4], [6,7,8]. The same walk fails the instant a window crosses a value that doesn’t exist. Here it is collapsing on a divisibility-valid hand — watch the dashed ghost cell in the (4, 5, 6) window:

hand[1, 2, 3, 2, 3, 4, 4, 6, 7]groupSize3

Sorted distinct values — remaining copies

·11

·22

·32

·42

·61

·71

groups locked innone yet

1 / 8

group start (smallest remaining)consumed into the groupneed check (count 0)missing card / strandedused up

Second trace: the same sweep rejecting a hand — counts are 1 x1, 2 x2, 3 x2, 4 x2, 6 x1, 7 x1, groupSize = 3. The divisibility gate passes (9 % 3 == 0), so this rejection has to come from inside the sweep itself.

Card 5 never existed, so the run (4, 5, 6) can never be completed, and the stranded card 4 ends the hand. (The statement’s second example, [1,2,3,4,5] with groupSize = 4, is rejected even earlier — 5 mod 4 is 1, so the divisibility check at the top never lets the sweep run.)

Why it’s correct: processing values in sorted order guarantees that by the time we look at start, every group that could have started before start has already been accounted for — so any copies of start still remaining absolutely must begin new groups at start (there is no earlier value left to anchor them to). Committing to that is never a mistake, because delaying it is not even an option: a smaller unused card would have to be the start of its own group, and start is the smallest one left. Complexity: sorting the distinct values is O(n log n); the consumption pass touches each value O(groupSize) times but does O(1) work per group formed, so it does not dominate. Space is O(n) for the counter.