LeetCode 846 · Greedy

Hand of Straights, explained with a picture

Laying a hand of cards out as runs.

MediumGreedy
▶ Watch it step by step

The problem

Can a hand of cards be split into groups of groupSize consecutive values (like 1-2-3)? Every card must be used.

Input:  hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
Output: true   ([1,2,3], [2,3,4], [6,7,8])

Picture it

Picture laying cards out as runs on a table. The smallest card left must start a run (nothing smaller can come before it). So we take it and the next groupSize − 1 values above it; if any is missing, it’s impossible. Repeat until the hand is empty.

How to recognise it

  • You must split a multiset of numbers into groups of consecutive values of a fixed size.
  • The smallest remaining card has no choice: it cannot sit in the middle of a run (nothing smaller is left), so it must start a run. That forced choice is the greedy step.
  • Values can be as large as 10^9, so you cannot use an array indexed by value; a counter (a dictionary of counts) is the natural tool.
  • Up to 10^4 cards: repeatedly searching the list is O(n²), while counting is near linear.

Start with brute force

Sort the cards, take the smallest one, and remove it together with the next size - 1 consecutive values from the list. Fail if one is missing. Repeat until no cards are left.

def straight_brute(hand, size):
    cards = sorted(hand)
    while cards:
        low = cards[0]
        for v in range(low, low + size):
            if v not in cards:
                return False
            cards.remove(v)
    return True

Each v not in cards and remove scans the list, so time is O(n²): with 10^4 cards that is about 10^8 comparisons. Space is O(n) for the copy.

From brute force to the idea

  1. The smallest card is forced. If the smallest value v is still unused, every run containing it must start at v. Nothing smaller exists to come before it.
  2. Count instead of searching. Build count, a Counter (dictionary) of how many copies of each value remain.
  3. Visit values in increasing order. For each distinct value start, need = count[start] copies are left; they must all begin runs, so need runs start here.
  4. Use up the run. Each of those runs needs one card of each of start, start + 1, …, start + size - 1. If count[v] < need for any of them, there are not enough cards: return False. Otherwise subtract need from each.
  5. Finish. If every value was handled without failing, all cards were used, so return True. Reading count[v] for a missing value gives 0 without adding it, so the check is safe.

This is the key idea: always start runs at the smallest remaining value, and use counts to take all runs starting there at once.

The shown code also needs from collections import Counter.

The key idea

Count cards; always start a run at the smallest remaining value and consume the following values. O(n log n).

Python solution

def is_n_straight_hand(hand, size):
    count = Counter(hand)
    for start in sorted(count):
        need = count[start]              # runs that must start at this card
        if need:
            for v in range(start, start + size):
                if count[v] < need:
                    return False
                count[v] -= need
    return True

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): list search and removal for every cardO(n): the sorted copy
Counter greedy (shown code)O(n log n): sorting the distinct values; the run loops total about n steps, since each run uses size cardsO(n): the Counter

Edge cases

  • Empty hand: returns True (nothing to group).
  • Size 1 ([5], 1): returns True; every card is a group by itself.
  • Size bigger than the hand ([1, 2], 3): returns False, since count[3] is 0.
  • Not divisible ([1, 2, 3, 4], 3): returns False; the check fails at the second run. There is no separate length test.
  • Gap in values ([1, 2, 3, 4, 5], 4): returns False.
  • Overlapping runs ([3, 4, 5, 1, 2, 3], 3): returns True with runs 1-2-3 and 3-4-5, the repeated 3 starting a second run.
  • Large values (around 10^9): fine, the code only loops over size values per start.

Common mistakes

  • Iterating over the values in insertion order instead of sorted order: [3, 2, 1] with size 3 wrongly returns False.
  • Removing one run at a time without using counts, which gives O(n²).
  • Using a plain dictionary and reading a missing key, which raises KeyError (a Counter returns 0).
  • Checking only that the length is a multiple of the size, which is necessary but not enough.
Your turn: report the runs

Instead of yes or no, return the sorted list of starting values of the runs (a value that starts two runs appears twice), or None if the hand cannot be split. For [1, 2, 3, 6, 2, 3, 4, 7, 8] with size 3 the answer is [1, 2, 6]. Describe your approach, then write it if you like.

Compare with our answer

Same loop, but record need copies of start when you consume the cards.

def run_starts(hand, size):
    count = Counter(hand)
    starts = []
    for start in sorted(count):
        need = count[start]
        if need:
            for v in range(start, start + size):
                if count[v] < need:
                    return None
                count[v] -= need
            starts += [start] * need
    return starts

run_starts([3, 4, 5, 1, 2, 3], 3) is [1, 3] and run_starts([1, 2, 3, 4], 3) is None. Time O(n log n), space O(n).

A strong answer mentions: processing values in sorted order, the smallest remaining value being forced to start need runs, subtracting need from every value in each run, and returning None as soon as a count is too small.

Check what stuck

1. Event tickets carry numbers, and you must seat guests in blocks of exactly k consecutive ticket numbers, using every ticket, with up to 10,000 tickets and numbers up to a billion. Which approach fits best?

2. Why is the shown code O(n log n) rather than O(n × size)?

3. A learner changes for start in sorted(count): to for start in count: (insertion order). Which input now returns the wrong answer?

Score 60% or more and the lesson is marked complete.