846. Hand of Straights
mediumDecide whether a hand of cards can be split into groups of consecutive integers of a given size. A clean min-heap + counter problem that hides a greedy core.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Constraints
1 <= hand.length <= 10^40 <= hand[i] <= 10^91 <= groupSize <= hand.length
Examples
Example 1
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3trueExplanation: Alice's hand can be rearranged as [1,2,3], [2,3,4], [6,7,8].
Example 2
hand = [1,2,3,4,5], groupSize = 4falseExplanation: Alice's hand can not be rearranged into groups of 4.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
If the total card count isn't divisible by groupSize, return false immediately.
Hint 2
Greedy insight: the smallest unused card must start a group. There's no other group it can fit into.
Hint 3
Use a min-heap (or sorted counter) of distinct values plus a count map. Peek the smallest, then consume groupSize consecutive values starting from it.
Hint 4
If any required next value is missing or has count 0, return false.
Solution approach
Reveal approach
Count occurrences of each card in a hash map. Push distinct values into a min-heap (or simply sort the unique values). The greedy core: the smallest available value must be the start of some group — no other group can contain a value smaller than this start. Pop the heap's min; for v in [min, min+groupSize): if count[v] is 0 the answer is false; otherwise decrement count[v]. Pop v from the heap whenever its count hits 0 to keep the heap clean. Continue until the heap is empty. O(n log n) from the sort/heap, plus O(n * groupSize) for the consume loop in the worst case — but each card is touched O(1) times in the count map. Edge case: groupSize == 1 always returns true.
Complexity
- Time
- O(n log n)
- Space
- O(n)
Related patterns
- heap
- greedy
- hash-map
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Hand of Straights and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →