Hand of Straights
You're given an array hand of card values and an integer groupSize. Return true if the cards can be rearranged into groups where every group has exactly groupSize cards with consecutive values, and every card is used in exactly one group.
Examples
hand = [5,3,4,6,4,5], groupSize = 3 returns true
The cards form [3,4,5] and [4,5,6].
hand = [2,3,3,4,5,7], groupSize = 3 returns false
The 2 must start [2,3,4]. The cards left over, 3, 5, and 7, aren't consecutive.
hand = [1,2,3,4], groupSize = 3 returns false
Four cards can't be split into groups of three.
Constraints
- 1 <= hand.length <= 10^4
- 0 <= hand[i] <= 10^9
- 1 <= groupSize <= hand.length
Hints
Think about the smallest card in the hand. Which group can it possibly belong to?
Greedy works: the smallest remaining card must start a group. Keep card counts in a sorted structure so you can always find it.
Count cards in a sorted map. For each value v in increasing order with count c > 0, subtract c from the counts of v + 1 through v + groupSize - 1, returning false if any would drop below 0.
Drill This: Your Approach First
Approach
The smallest card left can only be the start of a group, since nothing smaller remains to come before it. So greedily start a group at the smallest remaining value v and use one copy each of v, v + 1, ..., v + groupSize - 1, failing if any is missing. Keep counts in a sorted map and take every group starting at v at once by subtracting v's count from the next groupSize - 1 values. Check first that the hand size divides evenly. O(n log n) time for the sort, O(n) space.
Time
O(n log n)
Space
O(n)
Pitfall
Solutions
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) return false;
TreeMap<Integer, Integer> counts = new TreeMap<>();
for (int card : hand) counts.merge(card, 1, Integer::sum);
for (int start : counts.keySet()) {
int need = counts.get(start);
if (need == 0) continue;
for (int v = start; v < start + groupSize; v++) {
int have = counts.getOrDefault(v, 0);
if (have < need) return false;
counts.put(v, have - need);
}
}
return true;
}
}from collections import Counter
class Solution:
def isNStraightHand(self, hand, groupSize: int) -> bool:
if len(hand) % groupSize:
return False
counts = Counter(hand)
for start in sorted(counts):
need = counts[start]
if need == 0:
continue
for v in range(start, start + groupSize):
if counts[v] < need:
return False
counts[v] -= need
return True