Hand of Straights
Problem Statement
You are given an integer array hand, where hand[i] is a card value, and an integer groupSize. Return whether the cards can be rearranged into groups of size groupSize such that each group contains groupSize consecutive card values.
Input
An integer array hand and an integer groupSize.
Output
A boolean: true if the hand can be partitioned into consecutive groups of size groupSize, otherwise false.
Constraints
- •
1 <= hand.length <= 10^4 - •
0 <= hand[i] <= 10^9 - •
1 <= groupSize <= hand.length
Examples
Example 1
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
trueExample 2
hand = [1,2,3,4,5], groupSize = 4
falseExample 3
hand = [1,2,3,4,5,6], groupSize = 2
trueLearning Objectives
- Use the smallest remaining card to force the start of the next consecutive group.
- Maintain sorted counts with a **TreeMap** or equivalent ordered map.
- Explain why delaying the minimum remaining card is impossible in any valid grouping.
- Implement count consumption without accidentally reusing cards.
Intuition
The smallest remaining card has no smaller card available to appear before it. Therefore, if it belongs to any consecutive group of size groupSize, it must be the first card of that group. That removes all choice: once you see the current minimum, you must consume that value and the next groupSize - 1 values.
This is the greedy insight. Do not try to assemble arbitrary groups or pick from the middle. Always start from the smallest remaining card and force the only possible run beginning there. A sorted count map gives both pieces you need: the current minimum and the remaining multiplicities.
Common mistakes
- ×Starting groups from an arbitrary card instead of the smallest remaining card.
- ×Using a normal hash map without also processing keys in sorted order.
- ×Forgetting the early divisibility check for **hand.length % groupSize**.
- ×Removing a key too early or allowing a count to go negative.
Algorithm Explanation
Greedy strategy
Count all cards in sorted order. While cards remain, take the smallest remaining value start and try to consume start, start + 1, ... start + groupSize - 1 once each.
Why it works
The smallest remaining card cannot be placed anywhere except the beginning of a consecutive group, because there is no smaller card left to precede it. Once that group starts, all following values in the run are forced. If any required value is missing, no valid grouping can exist.
Proof of correctness
Take any valid partition of the current remaining cards. Let x be the smallest remaining card. In that partition, x must be in some consecutive group. Since no value smaller than x remains, x must be the first value of that group, so the group must contain x, x + 1, ... x + groupSize - 1. The greedy algorithm removes exactly this forced group. Removing a forced group from a valid partition leaves a valid partition of the remaining cards. Repeating the argument proves that if the greedy process never fails, it builds a valid partition, and if it fails, no valid partition could have existed at that step.
Algorithm
- If hand.length is not divisible by groupSize, return false.
- Build a sorted count map from card value to frequency.
- While the map is not empty, read the smallest key as start.
- For each value from start through start + groupSize - 1, require a positive count.
- Decrement each required count and remove the key when the count reaches zero.
- If every forced run is consumed, return true.
Solutions
Solution: TreeMap counts from smallest card
Use a sorted frequency map so the smallest remaining card is always available. Each iteration starts a forced run at that smallest card and consumes groupSize consecutive counts.
Step-by-step
- Return false immediately if the number of cards cannot split evenly into groups.
- Count every card value in a TreeMap.
- While counts remain, let start be the smallest key.
- For each consecutive value in the required run, check that the count exists.
- Decrement the count, removing the value when its count becomes zero.
- If all runs are consumed, return true.
O(n log n)
O(n)
Each card is consumed once, and every ordered-map operation costs O(log n) in the number of distinct values.
Java implementation
Dry Run
Sample input
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3. Initial counts are 1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1.
| run | card consumed | count before | action | smallest remaining after action |
|---|---|---|---|---|
| start at 1 | 1 | 1 | remove 1 | 2 |
| start at 1 | 2 | 2 | decrement to 1 | 2 |
| start at 1 | 3 | 2 | decrement to 1 | 2 |
| start at 2 | 2 | 1 | remove 2 | 3 |
| start at 2 | 3 | 1 | remove 3 | 4 |
| start at 2 | 4 | 1 | remove 4 | 6 |
| start at 6 | 6 | 1 | remove 6 | 7 |
| start at 6 | 7 | 1 | remove 7 | 8 |
| start at 6 | 8 | 1 | remove 8 | none |
Every smallest remaining card successfully starts a full consecutive run. After the final removal, no cards remain, so the hand can be partitioned.
Interview Tips
State the forced-choice argument clearly: the minimum remaining card must start a group. That single sentence is usually the proof interviewers want to hear. Also mention that the data structure can be a TreeMap, or a sorted array plus counts, as long as you repeatedly process values from smallest to largest.
Likely follow-ups
- How would you solve the same problem with sorting plus a hash map instead of a **TreeMap**?
- What if each group could have size at least **groupSize** instead of exactly **groupSize**?
- How would you return the actual groups, not just whether they exist?
- What changes if card values arrive as a stream and you cannot sort all of them upfront?
Similar Problems
Key Takeaways
- The smallest remaining card is forced to start a group.
- A sorted count map turns that forced choice into a simple loop.
- If any required consecutive value is missing, the failure is final, not local.
- Greedy grouping proofs often remove one forced group and recurse on the remainder.