Hand of Straights
Problem
Given an array of integers hand and an integer groupSize, return true if it is possible to rearrange the hand into groups of groupSize consecutive cards, and false otherwise.
- 1 ≤ hand.length ≤ 10⁴
- 0 ≤ hand[i] ≤ 10⁹
- 1 ≤ groupSize ≤ hand.length
Example
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3trueThe hand can be rearranged into groups [1,2,3], [2,3,4], and [6,7,8]. The algorithm first counts the frequency of each card, then uses a min-heap to always start forming groups from the smallest available card. For the first group, it picks 1, then checks for 2 and 3 consecutively, decrementing their counts. It continues this process until all cards are grouped or a consecutive card is missing, in which case it returns false.
Approach
Straightforward Solution
A brute-force approach might try all permutations or attempt to form groups arbitrarily, which is computationally infeasible due to factorial complexity and lack of structure.
Core Observation
The problem requires partitioning the multiset of cards into consecutive groups of fixed size. The fundamental truth is that to form consecutive groups, one must always start from the smallest available card to maintain order and avoid skipping cards that would break consecutiveness.
Path to Optimal
PreviewThe key recognition signals are 'consecutive groups', 'fixed group size', and 'rearrangement possible'. These indicate a greedy approach combined with a min-heap to always pick the smallest card available…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewCount the frequency of each card and build a min-heap of unique cards. While the heap is not empty, pick the smallest card and attempt to form a consecutive group of size groupSize by decrementing counts…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Building the frequency map takes O(n). Heapifying the unique cards takes O(k) where k is the number of unique cards. Each card is pushed and popped at most once, and each group formation involves up to groupSize heap operations, resulting in O(n log n) overall.
Space
O(n)
The frequency map and min-heap store up to n elements in the worst case, which is proportional to the input size. This auxiliary space is necessary to track card counts and ordering.
Pattern Spotlight
Heap / Priority Queue (Greedy Sequential Grouping)
Always process the smallest available element first to greedily form consecutive groups, using a min-heap to efficiently track and update the next candidate for grouping.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
|
| 5 | if len(hand) % groupSize:
|
| 6 | return False
|
| 7 |
|
| 8 | count = {}
|
| 9 | for n in hand:
|
| 10 | count[n] = 1 + count.get(n, 0)
|
| 11 |
|
| 12 | min_heap = list(count.keys())
|
| 13 | heapq.heapify(min_heap)
|
| 14 |
|
| 15 | while min_heap:
|
| 16 | first = min_heap[0]
|
| 17 | for i in range(first, first + groupSize):
|
| 18 | if i not in count:
|
| 19 | return False
|
| 20 | count[i] -= 1
|
| 21 | if count[i] == 0:
|
| 22 | if i != min_heap[0]:
|
| 23 | return False
|
| 24 | heapq.heappop(min_heap)
|
| 25 |
|
| 26 | return True |
Step-by-Step Solution
Validate Hand Length Divisibility by Group Size
| 5 | if len(hand) % groupSize:
|
| 6 | return False
|
Objective
To quickly reject hands that cannot be evenly divided into groups of the specified size.
Key Insight
If the total number of cards is not divisible by groupSize, it is impossible to partition the hand into equal-sized groups, so the function can return false immediately. This early check prevents unnecessary computation.
Interview Quick-Check
Core Logic
Checking divisibility of hand length by groupSize is a necessary condition for forming equal-sized groups.
Common Pitfalls & Bugs
Forgetting this check can lead to wasted computation on impossible cases.
Build Frequency Map of Cards
To count the occurrences of each card in the hand for tracking availability during grouping.
Initialize Min-Heap with Unique Cards
To maintain the smallest available card at the top for greedy group formation.
Greedily Form Consecutive Groups Using the Min-Heap
To iteratively form groups of consecutive cards starting from the smallest available card until all cards are grouped or a failure is detected.
Return True After Successful Grouping
To confirm that all cards have been grouped successfully and return true.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if i != min_heap[0]:Verify that the exhausted card is at the top of the heap before removal.
This check is critical because popping a card out of order would break the ascending grouping logic, potentially leaving cards ungrouped or causing incorrect groupings.
heapq.heapify(min_heap)Transform the list of unique cards into a min-heap.
Heapifying the unique cards is critical because it enables O(log n) access to the smallest card, which is necessary for the greedy grouping strategy to maintain ascending order.
first = min_heap[0]Peek at the smallest card currently available in the heap.
Accessing the smallest card without popping allows the algorithm to verify consecutive cards in order before modifying the heap, preserving correctness.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why must the algorithm always start forming groups from the smallest available card in the min-heap?
See the answer with Pro.
Related Problems
Heap / Priority Queue pattern
Don't just read it. Drill it.
Reconstruct Hand of Straights from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Hand of Straights drill