4.26.5 — Hand of Straights

LeetCode 846 · Medium

The problem

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

Restating the Problem: You are given an array of integers representing cards, and a groupSize. You need to rearrange the cards into groups where each group contains exactly groupSize cards, and the numbers in each group form a consecutive sequence (like [2,3,4]). Return true if possible.

• Constraints to note: The array length can be up to 10^5, meaning an O(n \log n) or O(n) solution is required.
• Edge cases: groupSize of 1 is always valid. If hand.length is not a multiple of groupSize, it's impossible.

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

Brute Force Approach

The naive approach is to simulate the process manually: find the minimum card, then repeatedly search the entire array to find the next consecutive card, remove it, and continue until a group is formed. Searching the array for each needed card takes O(n) time per card, resulting in O(n^2) total time. With N=10^5, this is too slow. We need a way to look up and consume cards efficiently.

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;
}

Code Walkthrough:

• Divisibility Check: First, if the total number of cards isn't divisible by groupSize, we immediately return False.
• Counting Cards: We use a hash map (or Counter) to count the frequency of each card.
• Sorting Unique Cards: We sort the unique cards to ensure we always start forming groups from the absolute smallest available card.
• Forming Groups: For each unique card, we check how many copies (needed) are left. If needed is zero, we've already used them up in earlier groups.
• Consuming the Sequence: If we need needed groups starting at card, we must also have at least needed copies of card + 1, card + 2, up to card + groupSize - 1. We check the count of each required card in the sequence. If we don't have enough, we return False. Otherwise, we subtract needed from their counts.
• Return: If we finish the loop without failing, all cards have been validly grouped.

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

• Time Complexity: O(n \log n + n \times \text{groupSize}). We count frequencies in O(n), then sort the unique keys in O(n \log n) (worst case if all cards are unique). The nested loop looks like it could be O(n^2), but each element's count is decremented at most once per group it participates in. Overall, the inner loop work is bounded by the total number of cards.
• Space Complexity: O(n) space for the hash map to store frequencies of the distinct values.

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.