Hand of Straights

Problem Description

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.

Note: This problem is also known as "Divide Array in Sets of K Consecutive Numbers" (LeetCode 1296).

Examples

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.

Example 3:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 1
Output: true
Explanation: Each card forms its own group.

Constraints

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

Solution Approach

This problem can be solved using a greedy approach combined with a frequency map and sorting:

Key Insight

To form groups of consecutive numbers:

1. We must be able to divide the total cards into equal groups
2. Each group must start with the smallest available card
3. Starting from the smallest card, we greedily try to form consecutive sequences

Algorithm

1. Check divisibility: If hand.length % groupSize != 0, return false (can't form equal groups)
2. Build frequency map: Count the frequency of each card value
3. Sort the hand: Process cards in ascending order
4. Form groups greedily:
   • For each card that still has available copies:
     • Try to form a consecutive group starting from this card
     • For i from 0 to groupSize-1, check if card+i exists with frequency > 0
     • If any card in the sequence is missing, return false
     • Decrement frequency for each card used in the group
5. Return true: If all groups formed successfully

Greedy Strategy

The greedy choice is to always start forming a group with the smallest available card. This ensures we don't "waste" smaller cards that might be needed for other groups.

Example Walkthrough

For hand = [1,2,3,6,2,3,4,7,8], groupSize = 3:

1. Frequency: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}
2. Sorted: [1,2,2,3,3,4,6,7,8]
3. Process:
   • Start at 1: Form [1,2,3], frequencies: {1:0, 2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
   • Start at 2: Form [2,3,4], frequencies: {1:0, 2:0, 3:0, 4:0, 6:1, 7:1, 8:1}
   • Start at 6: Form [6,7,8], frequencies: {1:0, 2:0, 3:0, 4:0, 6:0, 7:0, 8:0}
4. All cards used successfully → return true

Time & Space Complexity

• Time Complexity: O(n log n) where n is the number of cards (sorting dominates)
• Space Complexity: O(n) for the frequency map

Java Solution

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        // Check if it's possible to divide into equal groups
        if (hand.length % groupSize != 0) {
            return false;
        }

        // Count frequency of each card
        Map<Integer, Integer> freq = new HashMap<>();
        for (int card : hand) {
            freq.put(card, freq.getOrDefault(card, 0) + 1);
        }

        // Sort the hand
        Arrays.sort(hand);

        // Try to form consecutive groups
        for (int card : hand) {
            if (freq.get(card) > 0) {
                // Try to form a group starting from this card
                for (int i = 0; i < groupSize; i++) {
                    int needed = card + i;
                    if (freq.getOrDefault(needed, 0) == 0) {
                        return false; // Can't form consecutive group
                    }
                    freq.put(needed, freq.get(needed) - 1);
                }
            }
        }

        return true;
    }
}

Python Solution

def isNStraightHand(hand: List[int], groupSize: int) -> bool:
    # Check if it's possible to divide into equal groups
    if len(hand) % groupSize != 0:
        return False

    # Count frequency of each card
    from collections import Counter
    freq = Counter(hand)

    # Sort the hand
    hand.sort()

    # Try to form consecutive groups
    for card in hand:
        if freq[card] > 0:
            # Try to form a group starting from this card
            for i in range(groupSize):
                needed = card + i
                if freq[needed] == 0:
                    return False  # Can't form consecutive group
                freq[needed] -= 1

    return True

Alternative Approach: Min Heap

You can also solve this using a min heap to always process the smallest card:

public boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;

    Map<Integer, Integer> freq = new HashMap<>();
    for (int card : hand) {
        freq.put(card, freq.getOrDefault(card, 0) + 1);
    }

    PriorityQueue<Integer> minHeap = new PriorityQueue<>(freq.keySet());

    while (!minHeap.isEmpty()) {
        int first = minHeap.peek();
        for (int i = 0; i < groupSize; i++) {
            int card = first + i;
            if (!freq.containsKey(card)) return false;

            freq.put(card, freq.get(card) - 1);
            if (freq.get(card) == 0) {
                if (card != minHeap.peek()) return false;
                minHeap.poll();
            }
        }
    }

    return true;
}

This approach has the same time complexity but uses a heap for cleaner logic.