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 TrueFinding 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 TruePlay 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:
[1, 2, 3, 6, 2, 3, 4, 7, 8]groupSize3Sorted distinct values — remaining copies
Group window — 3 consecutive values
the smallest remaining card anchors the next window
Count copies and sort distinct values: 1 x1, 2 x2, 3 x2, 4 x1, 6 x1, 7 x1, 8 x1 with groupSize = 3. The smallest remaining card must 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:
[1, 2, 3, 2, 3, 4, 4, 6, 7]groupSize3Sorted distinct values — remaining copies
Group window — 3 consecutive values
the smallest remaining card anchors the next window
Second trace: the same sweep rejecting a hand. Divisibility passes (9 % 3 == 0), so the rejection must come from the sweep — watch the (4, 5, 6) window.
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.