#846 Hand of Straights
the problem
In plain words
Can the cards in hand be split into groups of size groupSize, where each group is groupSize consecutive values? (Same problem as LC 1296.)
in hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
out true
[1,2,3], [2,3,4], [6,7,8].
in hand = [1,2,3,4,5], groupSize = 4
out false
- 1 ≤ hand.length ≤ 10⁴
- 0 ≤ hand[i] ≤ 10⁹
- 1 ≤ groupSize ≤ hand.length
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy choiceOrdered map / set (floor & ceiling)
The smallest card left can only be the start of a group, since nothing smaller remains to come before it. So the greedy choice is forced: start a run there.
solutions
From brute force to optimal
Sort into an ArrayList. Repeatedly take the smallest and remove first+1, first+2, … by value.
- Sort.
- Remove the first card, then search and remove each next value.
- Fail if one is missing.
Each remove(Object) is an O(n) search plus an O(n) shift.
The list.
class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) return false; List<Integer> cards = new ArrayList<>(); for (int c : hand) cards.add(c); Collections.sort(cards); while (!cards.isEmpty()) { int first = cards.remove(0); // smallest card starts a group for (int k = 1; k < groupSize; k++) { if (!cards.remove(Integer.valueOf(first + k))) return false; // O(n) search + shift } } return true; }}Walk the sorted cards. A card that still has a count left must start a run, so consume c, c+1, …, c+groupSize−1 from the map.
- Return false if n % groupSize ≠ 0.
- Sort a copy; count every card in a HashMap.
- For each card c with count > 0: decrement c..c+groupSize−1, failing on a missing value.
The sort dominates. Each card is consumed exactly once across all runs, so the loops add only O(n).
The sorted copy and the map.
class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) return false; int[] cards = hand.clone(); Arrays.sort(cards); // smallest card first, once Map<Integer, Integer> count = new HashMap<>(); for (int c : cards) count.merge(c, 1, Integer::sum); for (int c : cards) { if (count.get(c) == 0) continue; // already used inside an earlier run for (int k = 0; k < groupSize; k++) { // c must START a run: c, c+1, ..., c+groupSize-1 int have = count.getOrDefault(c + k, 0); if (have == 0) return false; // gap in the run count.put(c + k, have - 1); } } return true; }}Count the cards in a TreeMap. Take firstKey() and consume one each of first..first+groupSize−1.
- Return false if n % groupSize ≠ 0.
- Count with merge.
- While not empty: start at firstKey and decrement the next groupSize values, failing on a gap.
Each card is counted and consumed once, at O(log n) per TreeMap call.
The map.
class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) return false; TreeMap<Integer, Integer> count = new TreeMap<>(); for (int c : hand) count.merge(c, 1, Integer::sum); while (!count.isEmpty()) { int first = count.firstKey(); // smallest card MUST start a group for (int k = 0; k < groupSize; k++) { int card = first + k; Integer have = count.get(card); if (have == null) return false; // gap in the run if (have == 1) count.remove(card); else count.put(card, have - 1); } } return true; }}in the room
How to say it in the interview
talk track
- Justify the forced choice: "the minimum card can't be in the middle of a run, since nothing smaller is left."
- Then pick a structure that always knows the minimum: a TreeMap, or a sorted array walked once.
traps
- Forgetting the quick
n % groupSizecheck. - Sorting a HashMap's keys again every round instead of using a TreeMap (or sorting once).
what they ask next
Follow-ups
Faster in practice?
The sort-once + HashMap version above avoids a tree operation per card. Both are O(n log n) because of the sort.
before you submit
Edge cases to test
- hand.length % groupSize ≠ 0 → false straight away.
- groupSize = 1 → always true.
- Duplicates: [1,1,2,2,3,3] with groupSize 3 → two runs of [1,2,3].
practise next
Similar problems
- #128Longest Consecutive SequenceMediumin Hashing
- #767Reorganize StringMediumin Heaps