Hand of Straights

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.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

Constraints:

1 <= hand.length <= 10^4
0 <= hand[i] <= 10^9
1 <= groupSize <= hand.length

Solution

Approach 1: Greedy with Counter

The key insight is to always form groups starting with the smallest available card, ensuring consecutive sequences.

Implementation

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        count = Counter(hand)

        for card in sorted(count.keys()):
            if count[card] > 0:
                # Number of groups starting with this card
                groups_needed = count[card]

                # Form groups starting with this card
                for i in range(groupSize):
                    if count[card + i] < groups_needed:
                        return False
                    count[card + i] -= groups_needed

        return True

Approach 2: Using Min Heap

import heapq
from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        count = Counter(hand)
        min_heap = list(count.keys())
        heapq.heapify(min_heap)

        while min_heap:
            first = min_heap[0]

            # Try to form a group starting with first
            for card in range(first, first + groupSize):
                if card not in count:
                    return False

                count[card] -= 1

                if count[card] == 0:
                    # Card must be the current minimum
                    if card != min_heap[0]:
                        return False
                    heapq.heappop(min_heap)

        return True

Complexity Analysis

Counter Approach:

Time Complexity: O(n log n), where n is number of cards. Sorting dominates.
Space Complexity: O(n) for the counter.

Heap Approach:

Time Complexity: O(n log n) for heap operations.
Space Complexity: O(n) for counter and heap.

Key Insights

Size Check: If hand size is not divisible by groupSize, impossible to form complete groups.
Greedy Start: Always start forming groups with the smallest available card.
Consecutive Requirement: Each group must have exactly groupSize consecutive cards.
Counter Strategy: Track remaining count of each card, decrement as we form groups.
Batch Processing: When we start with card x appearing k times, we need k complete groups starting with x.
Order Matters: Process cards in sorted order to ensure we don’t skip any required starting points.