Problem Breakdown
Alice has a collection of cards represented by integers in hand. The goal is to determine if we can partition this entire set into groups where:
- Each group contains exactly W cards.
- Cards within each group are consecutive (e.g.,
[3, 4, 5]).
Inputs:
hand: A list of integers representing card values.W: The required size for every straight hand group.
Outputs:
- Boolean (
Trueif possible,Falseotherwise).
Implicit Constraints & Edge Cases:
- Partitioning Requirement: Every single card in the input array must belong to exactly one valid group. This implies that
len(hand)must be divisible byW. If not, it’s immediately impossible. - Value Range: Card values can go up to . We cannot use a frequency array (bucket sort) based on value; we must rely on hash maps or sorting.
- Duplicates: The problem allows duplicate card values across different groups (e.g., two
3s in the hand could start two separate sequences). Our logic must handle counts correctly, not just presence/absence of unique numbers.
Intuition
A brute-force approach would try to generate all permutations or subsets to find valid groupings, which is computationally impossible () for .
Key Insight: Consider the smallest card currently available in our hand (the global minimum). This specific instance must be part of a sequence starting at that value. Why? Because if it were not the start, there would need to be smaller cards preceding it to form its group. Since we are processing from the smallest upwards, any remaining copy of this card cannot be “covered” by an earlier number (as none exist). Therefore, every instance of the current minimum available card must initiate a new straight hand sequence starting at itself.
Optimal Strategy:
- Count frequencies of all cards using a hash map (
Counter). - Sort unique keys to process numbers from smallest to largest.
- For each number
cin sorted order: if we have remaining instances, they must start new groups. We verify that the required consecutive successors () exist with sufficient counts and decrement them accordingly.
Approach
- Validation: Check if total cards are divisible by
W. If not, returnFalseimmediately as we cannot form full-sized groups without leftovers. - Frequency Map: Create a frequency map (Counter) of the hand to track available counts for each card value efficiently ().
- Sorted Iteration: Extract unique keys from the counter and sort them in ascending order. This ensures we always handle the smallest remaining cards first, which is critical because they dictate where groups must start.
- Greedy Grouping Loop:
- Iterate through each sorted card
c. - While there are instances of
cleft (count[c] > 0):- This instance forces a group starting at
c. We need to find consecutive successors. - Check if every required successor () exists in the map and has sufficient count (at least equal to current needed). If any is missing or insufficient, return
False. - Decrement counts for all cards involved in this group (
cthroughc+W-1) by 1. This simulates removing them from hand as they are used up.
- This instance forces a group starting at
- Iterate through each sorted card
- Success: If we successfully process the loop without returning
False, it means a valid partition exists. ReturnTrue.
Complexity Analysis
- Time Complexity: , where is the length of
hand.- Sorting unique keys takes (where ).
- The nested loops iterate through cards. In a valid scenario, every card in the input array is decremented exactly once across all group formations. Thus, the inner operations sum up to proportional to .
- Sorting dominates or matches linear scan depending on implementation details (sorting unique keys vs sorting full list).
- Space Complexity: for storing the frequency map and sorted distinct elements, where is the number of unique cards ().
Solution
from collections import Counter
def handOfStraights(hand: List[int], W: int) -> bool:
# If total length isn't divisible by group size, we can't partition perfectly.
if len(hand) % W != 0:
return False
count = Counter(hand)
# Sort unique card values to process from smallest available number upwards.
sorted_cards = sorted(count.keys())
for card in sorted_cards:
# While there are instances of this specific card remaining,
# they must start a new group because no smaller numbers exist to cover them.
while count[card] > 0:
# Check if all required consecutive cards (W-1 successors) exist and have sufficient counts.
for i in range(1, W):
next_card = card + i
if not (next_card in count and count[next_card] > 0):
return False
# Decrement the usage of all cards involved in this specific group formation.
# We decrement by 1 because we are forming one instance of a straight hand here.
for i in range(W):
count[card + i] -= 1
return True
Edge Cases Handled
- Non-divisible Length: The code explicitly checks
len(hand) % W != 0at the start to handle cases where leftovers would make a valid partition impossible. - Missing Consecutive Cards: If iterating through sorted keys, if we encounter a card that requires successors (e.g.,
[1],W=2) but those successors don’t exist in the map or have count 0, the check inside the loop returnsFalse. - Large Values (): Using a hash map (
Counterand dictionary lookups) handles sparse large integers without memory overflow issues associated with array-based frequency counting. - Duplicates: The logic relies on counts (frequency), ensuring that multiple copies of the same number are treated as distinct resources for starting different groups or extending sequences appropriately.