Problem Description

The "Hand of Straights" problem asks you to determine if a list of integers hand can be rearranged into groups of size groupSize, where each group consists of groupSize consecutive numbers.

Each number in hand must be used exactly once, and no number can appear in more than one group. If it's possible to split the entire hand this way, return True; otherwise, return False.

Key Constraints:

• Each group must be exactly groupSize and contain consecutive numbers.
• All elements from hand must be used; none can be left out or reused.
• There may be only one valid way to arrange the groups, or none at all.

Thought Process

At first glance, one might think of forming all possible groups by brute-force, checking every combination of groupSize consecutive numbers. However, this quickly becomes infeasible as the size of hand grows, due to the combinatorial explosion.

Instead, the problem is similar to dealing cards into straight hands in a card game. We need a systematic way to always pick the smallest available card and try to build a straight of length groupSize from it, repeating until all cards are used. This leads to the insight that we should process the hand in sorted order and track the count of each card.

Using a frequency count (hash map or dictionary), we can efficiently keep track of which numbers are available and how many times. By always starting with the smallest available card, we ensure we don't leave any gaps or impossible-to-fill groups for later.

Solution Approach

Let's break down the optimized solution step by step:

1. Check divisibility: If the size of hand isn't divisible by groupSize, it's impossible to form groups of equal size. Return False immediately.
2. Count frequencies: Use a hash map (dictionary) to count how many times each number appears in hand.
3. Sort unique cards: Sort the unique numbers in ascending order. This ensures we always try to build groups starting from the smallest available number.
4. Form groups: For each unique card in sorted order:
   • If its count is zero, skip it (it has already been used up in previous groups).
   • Otherwise, attempt to build a group starting from this card. For each offset i from 0 to groupSize-1:
     • Check if card + i exists in the count map and has at least as many cards as needed.
     • If not, return False (can't form a group).
     • Otherwise, decrement the count for card + i by the number of groups we're currently forming (which is the count of the starting card).
5. All cards used: If we finish processing all unique cards without returning False, it means we've successfully formed all groups. Return True.

Design Justification: We use a hash map for O(1) lookups and updates, and process cards in sorted order to avoid leaving "holes" that would make forming consecutive groups impossible later on.

Example Walkthrough

Let's walk through hand = [1,2,3,6,2,3,4,7,8] with groupSize = 3:

1. Step 1: Frequency count is {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}
2. Step 2: Process numbers in order: [1,2,3,4,6,7,8]
3. Step 3: Start with 1 (count=1). Try to form group [1,2,3]:
   • 1: count 1 → use 1 (now 0 left)
   • 2: count 2 → use 1 (now 1 left)
   • 3: count 2 → use 1 (now 1 left)
4. Step 4: Next is 2 (count=1). Try to form group [2,3,4]:
   • 2: count 1 → use 1 (now 0 left)
   • 3: count 1 → use 1 (now 0 left)
   • 4: count 1 → use 1 (now 0 left)
5. Step 5: Next is 3 (count=0), skip.
6. Step 6: Next is 4 (count=0), skip.
7. Step 7: Next is 6 (count=1). Try to form group [6,7,8]:
   • 6: count 1 → use 1 (now 0 left)
   • 7: count 1 → use 1 (now 0 left)
   • 8: count 1 → use 1 (now 0 left)
8. Step 8: All cards used with no failures. Return True.

Time and Space Complexity

Brute-force approach: Would involve generating all possible groupings and checking if any arrangement works. This is exponential in time complexity (O(n!)), which is infeasible for large inputs.

Optimized approach:

• Time Complexity: O(N log N), where N is the length of hand. This comes from sorting the unique card values. All other operations (count updates and lookups) are O(N).
• Space Complexity: O(N), for the frequency map and the list of unique cards.

Summary

The "Hand of Straights" problem is elegantly solved by counting card frequencies and always forming groups starting from the lowest available card. This greedy, frequency-based approach ensures that no cards are left unused or impossible to group later, and is far more efficient than brute-force. The key insight is to use a hash map for fast lookups and to process cards in sorted order, leveraging the properties of consecutive groups. This technique is widely applicable to similar problems involving grouping and ordering constraints.

Code Implementation

from collections import Counter

class Solution:
    def isNStraightHand(self, hand, groupSize):
        if len(hand) % groupSize != 0:
            return False
        count = Counter(hand)
        for key in sorted(count):
            occur = count[key]
            if occur > 0:
                for i in range(groupSize):
                    if count[key + i] < occur:
                        return False
                    count[key + i] -= occur
        return True
      

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false;
        map<int, int> count;
        for (int card : hand) count[card]++;
        for (auto it = count.begin(); it != count.end(); ++it) {
            int card = it->first;
            int occur = it->second;
            if (occur > 0) {
                for (int i = 0; i < groupSize; ++i) {
                    if (count[card + i] < occur) return false;
                    count[card + i] -= occur;
                }
            }
        }
        return true;
    }
};
      

import java.util.*;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        TreeMap<Integer, Integer> count = new TreeMap<>();
        for (int card : hand) count.put(card, count.getOrDefault(card, 0) + 1);
        for (int card : count.keySet()) {
            int occur = count.get(card);
            if (occur > 0) {
                for (int i = 0; i < groupSize; ++i) {
                    int next = card + i;
                    if (count.getOrDefault(next, 0) < occur) return false;
                    count.put(next, count.get(next) - occur);
                }
            }
        }
        return true;
    }
}
      

var isNStraightHand = function(hand, groupSize) {
    if (hand.length % groupSize !== 0) return false;
    let count = new Map();
    for (let card of hand) {
        count.set(card, (count.get(card) || 0) + 1);
    }
    let keys = Array.from(count.keys()).sort((a, b) => a - b);
    for (let key of keys) {
        let occur = count.get(key);
        if (occur > 0) {
            for (let i = 0; i < groupSize; ++i) {
                let next = key + i;
                if ((count.get(next) || 0) < occur) return false;
                count.set(next, count.get(next) - occur);
            }
        }
    }
    return true;
};