Hand of Straights
Decide whether cards can be split into groups of consecutive values: the smallest card left must start a group, so build groups greedily from it.
Problem Understanding
Hand of Straights: given card values hand and a groupSize, return true if the cards can be rearranged into groups of groupSize consecutive values, using every card exactly once.
Example: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3 returns true: [1, 2, 3], [2, 3, 4], [6, 7, 8].
The Intuition: The Smallest Card Has No Choice
Look at the smallest card left. It has to be in some group, and a group is a run of consecutive values, so the group must start with it. Nothing about that is a guess, which is why a greedy pass is correct.
- If
len(hand)is not a multiple ofgroupSize, returnfalse. - Count every value and walk the distinct values from smallest to largest.
- If
needcopies of the current value are left,needgroups start here. Each of the nextgroupSize − 1values must have at leastneedcopies; take them. - If any value runs short, return
false. If the walk finishes, returntrue.
The counting is the same idea as Top K Frequent Elements: a map from value to how many are left.
Interactive Walkthrough
Each column is a card value with the number of copies still unplaced. The smallest value with copies left is outlined: groups start there. Watch the counts of the following values drop as each group is completed.
Dry Run Table
Input: [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.
| Smallest left | Groups started | Takes | Counts after |
|---|---|---|---|
| 1 | 1 | 1, 2, 3 | 2×1, 3×1, 4×1, 6, 7, 8 |
| 2 | 1 | 2, 3, 4 | 6×1, 7×1, 8×1 |
| 3, 4 | 0 | — | skipped |
| 6 | 1 | 6, 7, 8 | all 0 |
Every card is used: true.
The Solution Template
Sorted counts, then greedy groups from the smallest value. The C snippet sorts the cards and builds one group at a time with a used flag.
Hand of Straights Code
1var isNStraightHand = function(hand, groupSize) {2 if (hand.length % groupSize) return false;3 const count = new Map();4 for (const card of hand) count.set(card, (count.get(card) || 0) + 1);5 for (const start of [...count.keys()].sort((a, b) => a - b)) {6 const need = count.get(start);7 if (need === 0) continue;8 for (let card = start; card < start + groupSize; card++) {9 if ((count.get(card) || 0) < need) return false;10 count.set(card, count.get(card) - need);11 }12 }13 return true;14};
Edge Cases & Common Mistakes
- Size not a multiple: return
falsebefore counting. - groupSize = 1: every card is its own group: always
true. - Gaps in values:
count[card]for a missing value is 0, which correctly fails. - Starting groups at any card: only the smallest remaining card is a safe start; starting elsewhere can strand smaller cards.
Summary
The smallest card left must start a group. Count the values, walk them in increasing order, and for each value with need copies left, take need copies of each of the next groupSize − 1 values; fail if any runs short. O(n log n) for the sorted keys.
More practice: DSA interview questions with answers · patterns cheat sheet