top of page

Hand of Straights: Greedy With a Sorted Counter

Nov 2
1 min read

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.

 
 
 

Recent Posts

See All
Image Smoother (LeetCode 661): Clean Neighbor Loops

For each cell of a grayscale image, replace it with the floor of the average of itself and its up to eight neighbors. Idea Loop over the 3x3 block around each cell, skip coordinates outside the grid,

 
 
 

Comments


bottom of page