Domain 2MediumMEDIUM

Hand of Straights

LeetCode problem 846: Hand of Straights (medium).

Domain: medium•Updated: 2026-09-02
#Ordered Map

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:

  1. Each group contains exactly W cards.
  2. 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 (True if possible, False otherwise).

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 by W. If not, it’s immediately impossible.
  • Value Range: Card values can go up to 10910^9. 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 (O(N!)O(N!)) for N=104N=10^4.

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:

  1. Count frequencies of all cards using a hash map (Counter).
  2. Sort unique keys to process numbers from smallest to largest.
  3. For each number c in sorted order: if we have remaining instances, they must start new groups. We verify that the required consecutive successors (c+1…c+W−1c+1 \dots c+W-1) exist with sufficient counts and decrement them accordingly.

Approach

  1. Validation: Check if total cards are divisible by W. If not, return False immediately as we cannot form full-sized groups without leftovers.
  2. Frequency Map: Create a frequency map (Counter) of the hand to track available counts for each card value efficiently (O(N)O(N)).
  3. 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.
  4. Greedy Grouping Loop:
    • Iterate through each sorted card c.
    • While there are instances of c left (count[c] > 0):
      • This instance forces a group starting at c. We need to find W−1W-1 consecutive successors.
      • Check if every required successor (c+1,…,c+W−1c+1, \dots, c+W-1) 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 (c through c+W-1) by 1. This simulates removing them from hand as they are used up.
  5. Success: If we successfully process the loop without returning False, it means a valid partition exists. Return True.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N), where NN is the length of hand.
    • Sorting unique keys takes O(Ulog⁡U)O(U \log U) (where U≤NU \le N).
    • 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 NN.
    • Sorting dominates or matches linear scan depending on implementation details (sorting unique keys vs sorting full list).
  • Space Complexity: O(U)O(U) for storing the frequency map and sorted distinct elements, where UU is the number of unique cards (U≤NU \le N).

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 != 0 at 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 returns False.
  • Large Values (10910^9): Using a hash map (Counter and 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.