Core Insight Commit to the locally best safe choice only after identifying why it cannot block an optimal answer.
Common Pitfall Sort or define the selection order before applying the greedy rule.
Description
Determine if hand can be rearranged into groups of groupSize consecutive cards.
Constraints
- Time Complexity:
O(n log n) - Space Complexity:
O(n)
Tags
arrayhash-mapgreedysorting
Implementation Plan Translate the invariant into these small, testable moves.
- Order candidates by the greedy criterion.
- Inspect the next candidate.
- Accept it only when it preserves feasibility.
- Return the accumulated result.
def isNStraightHand(hand, groupSize):
if len(hand) % groupSize:
return False
count = {}
for n in hand:
count[n] = 1 + count.get(n, 0)
minH = list(count.keys())
heapq.heapify(minH)
while minH:
first = minH[0]
for i in range(first, first + groupSize):
if i not in count:
return False
count[i] -= 1
if count[i] == 0:
if i != minH[0]:
return False
heapq.heappop(minH)
return True