The problem
Given the values of a hand of cards and a groupSize, return true if the cards can be rearranged into groups of groupSize consecutive values, each card used once.
Examples
01
- Input
hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
- Output
true
02
- Input
hand = [1, 2, 3, 4, 5], groupSize = 4
- Output
false
Constraints
- 1 ≤ hand.length ≤ 10⁴
- 0 ≤ hand[i] ≤ 10⁹
- 1 ≤ groupSize ≤ hand.length
The idea
Look at the smallest card left. Nothing smaller remains to go before it, so it must start a group: that group needs the next groupSize − 1 values.
Count the cards, and go through the values in increasing order. If a value still has n copies, n groups must start there, so take n of each of the next values; if any is short, the answer is false. Handling a whole count at once, instead of one group at a time, keeps it fast.
- Time
- O(n log n) — sorting the distinct values
- Space
- O(n)
Solution · every language run against every case
class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: if len(hand) % groupSize: return False count = Counter(hand) # The smallest card left must start a run — nothing smaller is left to come before it. for card in sorted(count): n = count[card] if n == 0: continue for x in range(card, card + groupSize): # n runs start here, each needing card..card+size-1 if count[x] < n: return False count[x] -= n return True