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
- 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.
- Count instead of searching. Build
count, a Counter (dictionary) of how many copies of each value remain. - Visit values in increasing order. For each distinct value
start,need = count[start]copies are left; they must all begin runs, soneedruns start here. - Use up the run. Each of those runs needs one card of each of
start, start + 1, …, start + size - 1. Ifcount[v] < needfor any of them, there are not enough cards: returnFalse. Otherwise subtractneedfrom each. - Finish. If every value was handled without failing, all cards were used, so return
True. Readingcount[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 TrueLeetCode 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): list search and removal for every card | O(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 cards | O(n): the Counter |
Edge cases
- Empty hand: returns
True(nothing to group). - Size 1 (
[5], 1): returnsTrue; every card is a group by itself. - Size bigger than the hand (
[1, 2], 3): returnsFalse, sincecount[3]is 0. - Not divisible (
[1, 2, 3, 4], 3): returnsFalse; the check fails at the second run. There is no separate length test. - Gap in values (
[1, 2, 3, 4, 5], 4): returnsFalse. - Overlapping runs (
[3, 4, 5, 1, 2, 3], 3): returnsTruewith 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
sizevalues per start.
Common mistakes
- Iterating over the values in insertion order instead of sorted order:
[3, 2, 1]with size 3 wrongly returnsFalse. - 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(aCounterreturns 0). - Checking only that the length is a multiple of the size, which is necessary but not enough.
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.
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?
The smallest remaining number must start a block, and counts let you handle all blocks that start there together in O(n log n). An array over a billion values wastes memory, and chunking a sorted list breaks when numbers repeat or have gaps.
2. Why is the shown code O(n log n) rather than O(n × size)?
The number of runs times size equals the number of cards, so the inner loop does about n steps overall, and sorting the distinct values costs O(n log n). A Counter is not sorted, and the early return happens only on failure.
3. A learner changes for start in sorted(count): to for start in count: (insertion order). Which input now returns the wrong answer?
For [3, 2, 1] the first key is 3, which would have to start a run 3, 4, 5; 4 is missing, so the learner's code returns False although 1, 2, 3 is a valid run. For the other three inputs the insertion order happens to still give the right answer (True each time).
Score 60% or more and the lesson is marked complete.