Hand of Straights: Greedy With a Sorted Counter
Hand of Straights asks whether a hand of cards can be split into groups of size W where each group is W consecutive values. It looks like a search problem, but a greedy rule solves it in O(n log n).
The greedy rule
Take the smallest card still in the hand. It cannot be in the middle or end of a group, because nothing smaller is left to come before it. So it must start a group, and that group must be x, x+1, ..., x+W-1. Remove those cards and repeat.
Code
from collections import Counter
def is_n_straight_hand(hand, w):
if len(hand) % w:
return False
count = Counter(hand)
for x in sorted(count):
need = count[x]
if need == 0:
continue
for v in range(x, x + w):
if count[v] < need:
return False
count[v] -= need
return True
Processing all copies of the smallest value at once (the need variable) keeps the loop at O(k * W) after sorting the k distinct values.
Why the proof matters
Interviewers often ask "why is greedy safe here?" The one-sentence answer is the exchange argument above: the minimum card has only one possible role. Say it before you code.
Variants
The same code solves "Divide Array in Sets of K Consecutive Numbers". If values are huge and sparse, a min-heap of distinct values works instead of sorting. For more interview walk-throughs and live practice, see Linkjob.
Disclosure: I help build Linkjob AI.
Comments