#846
Hand of Straights
Medium Smallest card starts a group
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether cards can be split into groups of groupSize consecutive values.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: split cards into groups of consecutive values.
Why this works: the smallest remaining card must start a group; take the next values right after it.
Example: [1,2,3,6,2,3,4,7,8], size 3
[1,2,3], [2,3,4], [6,7,8] ✓✦Hints open one at a time
The smallest remaining card must start a group.
Use a TreeMap of counts so you can always find the smallest.
↗Approach
While cards remain, take the smallest value v with count c; values v..v+groupSize−1 must each have at least c cards — subtract c from each.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) return false;
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int x : hand) count.merge(x, 1, Integer::sum);
while (!count.isEmpty()) {
int start = count.firstKey(), c = count.get(start); // c groups start here
for (int v = start; v < start + groupSize; v++) {
Integer have = count.get(v);
if (have == null || have < c) return false;
if (have == c) count.remove(v);
else count.put(v, have - c);
}
}
return true;
}
}!Common mistake
Forgetting the quick check n % groupSize != 0.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Greedy
🎬 Episodes 69–73: video coming soon