4.26.5 — Hand of Straights

LeetCode 846 · Medium

The problem

Can the hand be split entirely into groups of exactly groupSize consecutive cards?

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3   →  true
    [1,2,3], [2,3,4], [6,7,8]

hand = [1,2,3,4,5], groupSize = 4           →  false

The pattern

The greedy rule is forced, and seeing why it is forced is the point:

The smallest remaining card must start a group.

Nothing smaller exists to sit before it, so if it does not begin a group, it can never be part of one at all. There is no choice to make.

Once the starting card is fixed, the whole group is determined: it must be start, start+1, …, start+groupSize-1. If any of those is missing, the answer is false.

So the algorithm is: repeatedly take the smallest remaining card, remove the group it forces, and fail the moment a required card is absent.

A greedy with no choice at all is the easiest kind to justify — there is nothing to prove beyond "the smallest card has to go somewhere, and only one place is available".

The size check

If len(hand) is not divisible by groupSize, the answer is immediately false. One line, and it removes a class of inputs before any work.

The solution

Python

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False

        count = Counter(hand)

        for card in sorted(count):                # smallest first
            needed = count[card]
            if needed == 0:
                continue                          # already consumed by earlier groups

            for c in range(card, card + groupSize):
                if count[c] < needed:
                    return False                  # not enough of this card
                count[c] -= needed

        return True

TypeScript

function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;

  const count = new Map<number, number>();
  for (const c of hand) count.set(c, (count.get(c) ?? 0) + 1);

  for (const card of [...count.keys()].sort((a, b) => a - b)) {
    const needed = count.get(card)!;
    if (needed === 0) continue;

    for (let c = card; c < card + groupSize; c++) {
      const have = count.get(c) ?? 0;
      if (have < needed) return false;
      count.set(c, have - needed);
    }
  }

  return true;
}

Starting needed groups at once is the optimisation that makes this clean. If three cards of value 5 remain, then three groups must begin at 5 — there is no other option — so consume three of each of 5, 6, 7 in one step rather than looping three times.

if needed == 0: continue skips cards fully consumed by earlier groups.

Iterating over the sorted distinct values, not the raw hand, is what keeps the outer loop short.

Trace

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3. Counts: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}.

card	needed	consumes	counts after
1	1	one each of 1, 2, 3	{2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
2	1	one each of 2, 3, 4	{6:1, 7:1, 8:1}
3	0	skipped
6	1	one each of 6, 7, 8	{}

True ✓.

The heap alternative

If the values were huge or sparse, sorting the distinct keys is still fine — but a min-heap of the distinct values gives the same behaviour and is the version you would see in a streaming setting:

import heapq
heap = list(count.keys())
heapq.heapify(heap)
while heap:
    card = heap[0]
    if count[card] == 0:
        heapq.heappop(heap)
        continue
    ...

Same complexity. The sorted version is shorter and easier to explain.

Complexity

O(n \log n + n \times \text{groupSize}) — the sort, then each card consumed once per group it belongs to.

O(n) space for the counter.

In the worst case, when groupSize is large, the inner loop dominates. Note that the total work across all groups is bounded by the number of cards, since each card is decremented once per group that uses it and every card ends at zero.

Where this goes next

• Divide Array in Sets of K Consecutive Numbers (LeetCode 1296) — the identical problem with different wording. If you notice they are the same, you have solved both.
• Split Array into Consecutive Subsequences (LeetCode 659) — harder, because groups may be any length of at least 3, so there is a real choice: extend an existing run or start a new one. The greedy there is to prefer extending, and it needs an actual argument. Good contrast with this problem, where there was no choice at all.
• Task Scheduler — another counting greedy. 4.17.5.

What the interviewer will push on

"Why must the smallest card start a group?" Nothing smaller exists to precede it, so it has no other role.

"Why is the greedy safe?" There is no choice — the rule is forced, which is the easiest kind of greedy to justify.

"Why handle needed groups at once?" If k copies of a card remain, exactly k groups must start there.

"What if group sizes could vary?" That is LeetCode 659, and it does involve a choice, so it needs a real proof.

"What is the divisibility check for?" Every card must be used, and groups have fixed size.

One thing to volunteer: say "there is no choice here" out loud. Distinguishing a forced greedy from one that needs an exchange argument is exactly the judgement 4.25 is about.

Next: 4.26.6 Merge Triplets to Form Target Triplet — a greedy that becomes obvious once you notice which triplets are safe to use.