Deal the Cards Into Runs
MediumGreedy
Problem
A player holds cards with integer values hand. They want to lay all cards down as runs: groups of exactly groupSize cards with consecutive values (for example 4, 5, 6 when groupSize = 3). Every card must be in exactly one run.
Return true if this is possible, false otherwise.
Example 1
- Input:
- hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
- Output:
- true
Runs [1, 2, 3], [2, 3, 4] and [6, 7, 8].
Example 2
- Input:
- hand = [1, 2, 3, 4, 5], groupSize = 4
- Output:
- false
5 cards cannot be split into groups of 4.
Constraints
- 1 ≤ hand.length ≤ 10^5
- 0 ≤ hand[i] ≤ 10^9
- 1 ≤ groupSize ≤ hand.length
Hint
Show the first hint
Look at the smallest card. Which run can it possibly belong to?
Walkthrough
How to approach it
01Clarify before coding
- Can values repeat? Yes, and duplicates must go into different runs.
- Is groupSize = 1 allowed? Yes; then any hand works.
- Are values bounded? Up to 10^9, so use a hash map of counts rather than an array.
02Brute force
Backtracking: pick a card, try every run containing it, recurse on the rest.
Cost: Exponential in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.