count · card value below, copies left inside
minH · distinct values left, smallest first
Group being formed
Groups done
public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) { return false; } Map<Integer, Integer> count = new HashMap<>(); for (int n : hand) { count.merge(n, 1, Integer::sum); } PriorityQueue<Integer> minH = new PriorityQueue<>(count.keySet()); while (!minH.isEmpty()) { int first = minH.peek(); // smallest card left for (int i = first; i < first + groupSize; i++) { if (!count.containsKey(i)) { return false; } count.put(i, count.get(i) - 1); if (count.get(i) == 0) { if (i != minH.peek()) { return false; } minH.poll(); } } } return true;}
- first
- —
- i
- —
- count[i]
- —
- minH[0]
- —
- groups
- 0
Why it works
- Brute force sorts and rescans: repeatedly find the smallest card left, then search and remove the next
groupSize − 1values from the list. O(n²) with list removals. - The smallest card has no choice. Nothing smaller is left to precede it, so it must start a group:
first, first+1, …, first+groupSize−1. Greedily taking that run is forced, never a guess. - Counts plus a min-heap make each step cheap: the heap names the smallest value left, the map says how many copies remain. Each distinct value is pushed and popped once: O(n log n) time, O(n) space.
- Pitfall: when a count hits zero it must be the heap's top. If a middle value runs out first, as
2does in[1,1,2,3,3,4], the next group starting at the smaller leftover card would need that value again. Returnfalseright there. - Same problem: 1296 Divide Array in Sets of K Consecutive Numbers. Check
hand.length % groupSizefirst; it rules out Ex 2 before any work.