Problem Statement

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.

Additional information

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

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 not be rearranged into groups of 4.

Hash Map + Sorting (Standard)

Intuition

Before doing any heavy lifting, we must check a basic mathematical rule: if the total number of cards cannot be perfectly divided by the groupSize, it is completely impossible to group them. We return False immediately.

If the division is clean, we can count the frequency of every card using a Hash Map. Because the cards in a group must be consecutive, we must always start building our groups from the smallest available card.
We can extract all the unique cards, sort them, and iterate through them. If a card has a frequency greater than 0, it must be the start of a new group! We then check if the next groupSize - 1 consecutive numbers exist in our Hash Map with enough frequency to complete the group.

Algorithm

1. If len(hand) % groupSize != 0, return False.
2. Count the frequencies of all cards in hand using a Hash Map (Counter).
3. Extract the unique keys from the Hash Map and sort them.
4. Iterate through the sorted unique keys.
5. If the count of the current card is greater than 0:

• Store how many groups we need to form starting with this card (needed = count[card]).
• Loop i from card to card + groupSize - 1.
• If the frequency of i in the Hash Map is less than needed, we can't form the required groups. Return False.
• Subtract needed from count[i].

6. If we successfully iterate through all cards, return True.

def is_n_straight_hand(hand: list[int], group_size: int) -> bool:
    if len(hand) % group_size != 0:
        return False
        
    count = Counter(hand)
    
    # Sort the unique cards to always build from the smallest available
    for card in sorted(count.keys()):
        if count[card] > 0:
            # We must form 'needed' number of groups starting with this card
            needed = count[card]
            
            for i in range(card, card + group_size):
                if count[i] < needed:
                    return False
                count[i] -= needed
                
    return True

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: N is the total number of cards. Building the frequency map takes O(N). Sorting the unique keys takes up to O(N log N). The nested loop executes at most groupSize times per unique key, but since we subtract in bulk, it scales efficiently. Overall time is dominated by the sorting step.

• Space complexity: O(N)

• Reason: The Hash Map stores the frequencies of up to N unique cards.

Min-Heap (Optimal)

Intuition

Instead of sorting the keys once and iterating, we can use a Min-Heap (Priority Queue) to dynamically fetch the smallest available card.

We push all unique cards into the heap. The top of the heap is always our guaranteed starting point for the next straight. We try to build a sequence of length groupSize starting from that minimum card. Every time we use a card, we decrement its frequency.

If a card's frequency hits 0, it is completely exhausted. However, to maintain a valid consecutive sequence, the exhausted card must be the one at the top of our heap! If an inner card in our sequence hits 0 before the starting card does, it means a hole has formed in our sequence, making future groups impossible.

Algorithm

1. If len(hand) % groupSize != 0, return False.
2. Count the frequencies of all cards using a Hash Map.
3. Initialize a min_heap containing all the unique keys and heapify it.
4. While the min_heap is not empty:

• Peek at the top of the heap to find the starting card (first = min_heap[0]).
• Loop i from first to first + groupSize - 1.
• If count[i] is 0 or i doesn't exist, return False.
• Decrement count[i] by 1.
• If count[i] reaches 0:
• If i is not equal to min_heap[0], a required inner card was exhausted prematurely. Return False.
• Otherwise, safely pop the top of the heap.

5. Return True.

def is_n_straight_hand(hand: list[int], group_size: int) -> bool:
    if len(hand) % group_size != 0:
        return False
        
    count = Counter(hand)
    min_heap = list(count.keys())
    heapq.heapify(min_heap)
    
    while min_heap:
        first = min_heap[0]
        
        # Try to build a consecutive sequence
        for i in range(first, first + group_size):
            if count[i] == 0:
                return False
                
            count[i] -= 1
            
            # If a card is exhausted, it must be the top of the heap
            if count[i] == 0:
                if i != min_heap[0]:
                    return False
                heapq.heappop(min_heap)
                
    return True

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Heapifying the unique keys takes O(N) time. In the worst case, we push and pop N elements from the heap, which takes O(N log N) time.

• Space complexity: O(N)

• Reason: The Hash Map and the Min-Heap both hold up to N unique cards.