Description
Decide whether all integer-valued cards can be partitioned into groups of groupSize consecutive values. Each card occurrence is used once and groupSize is positive.
Solution
from collections import Counter
def is_n_straight_hand(hand, group_size):
if len(hand) % group_size:
return False
counts = Counter(hand)
for start in sorted(counts):
needed = counts[start]
if needed:
for value in range(start, start + group_size):
if counts[value] < needed:
return False
counts[value] -= needed
return TrueExamples
Example 1
- Input
[[1,2,3,6,2,3,4,7,8],3]- Output
true
Groups are 1-2-3, 2-3-4, and 6-7-8.
Example 2
- Input
[[1,2,3,4,5],4]- Output
false
The card count is not divisible by 4.
Example 3
- Input
[[1,1,2,2,3,3],3]- Output
true
Two identical consecutive groups are valid.
Approach
Count values and iterate distinct values in ascending order. If the smallest remaining value has count c, start c groups there and subtract c from every value in the next groupSize positions. Any insufficient count makes the partition impossible.
Time & space
O(n log n + n g) worst-case time and O(n) auxiliary space, where n is card count and g is groupSize.