LeetCode 846 · Greedy · concepts: greedy, hash-maps
Problem
Can the hand be rearranged into groups of groupSize consecutive cards?
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 -> true ([1,2,3],[2,3,4],[6,7,8])
Approach — count cards, greedily build from the smallest (optimal)
Count each value. Repeatedly take the smallest remaining card — it must start a group (nothing smaller exists to include it) — then consume the next groupSize − 1 consecutive values. If any is missing, fail. A min-heap or a sorted map surfaces the smallest.
import heapq
from collections import Counter
def isNStraightHand(hand, groupSize):
if len(hand) % groupSize != 0:
return False
count = Counter(hand)
heap = list(count.keys())
heapq.heapify(heap) # min-heap of distinct values
while heap:
smallest = heap[0]
for v in range(smallest, smallest + groupSize):
if count[v] == 0:
return False # missing a needed consecutive card
count[v] -= 1
if count[v] == 0:
if v != heap[0]:
return False # a hole opened up in the middle
heapq.heappop(heap)
return TrueTime O(n log n), space O(n).
Why start from the smallest
The smallest card can only ever be the left end of a group — no smaller card exists to sit before it. So it’s forced to start a straight, which forces the next groupSize−1 values. This “the extreme element has no choice” is the greedy anchor; each forced group is provably part of any valid arrangement.
Key insight
“Partition into consecutive/constrained groups” → greedily commit the forced element (the smallest) and let it dictate its group. Counting + always resolving the smallest first turns a combinatorial partition into a deterministic sweep. (Same idea solves Divide Array in Sets of K Consecutive Numbers.)
Related
- concepts: greedy, heaps, hash-maps
- prev: Gas Station · next: Merge Triplets to Form Target Triplet
Software engineering
Infrastructure & security
Computer science
Hardware & engineering