Hand of Straights — Greedy Grouping with an Ordered Frequency Map

Problem Statement#

Alice has some number of cards and wants to rearrange them 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 on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Constraints:

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

Input:  hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Groups [1,2,3], [2,3,4], [6,7,8].

Input:  hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: 5 cards cannot be divided into groups of 4.

Why This Problem Matters#

Hand of Straights (LC 846, identical to LC 1296 "Divide Array in Sets of K Consecutive Numbers") is a favourite at Google and Microsoft because it combines greedy algorithm design with ordered data structure selection. The key insight — always start a new group from the smallest available card — is a textbook greedy argument, and the sorted frequency map is the natural tool to implement it efficiently.

This problem teaches a widely applicable pattern: whenever you need to greedily consume items in order (smallest first), use a sorted structure. The same approach appears in task scheduling, interval merging, and partition problems across FAANG interviews.

At Microsoft, this problem tests whether candidates know that collections.Counter sorted by keys — or Java's TreeMap — gives them exactly what they need rather than a custom sort-and-scan approach. Interviewers also look for the early exit when len(hand) % groupSize != 0, which shows structured thinking before jumping into the main algorithm.

The Core Insight#

Greedy choice: Always start the next group with the smallest card that has not been fully consumed. If you skip the smallest remaining card, it can never be part of a consecutive group later — there is nothing smaller to pair it with on the left. So it is never beneficial to delay using the smallest card.

Algorithm:

1. Count frequencies using a hash map.
2. Sort the unique card values.
3. For each unique value in sorted order: if its frequency is still positive, form that many groups starting at this card. Consume one copy each of card, card+1, ..., card+groupSize-1. If any of these values has insufficient copies, return false.

Why batch by frequency? If value v has frequency f, all f copies must be the start of their own group (since v-1 is exhausted or does not exist). So all f groups can be started simultaneously.

Visual Dry Run#

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

Frequency map: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}

All frequencies zeroed. Return true.

Solution (Optimal)#

from collections import Counter
 
def isNStraightHand(hand: list[int], groupSize: int) -> bool:
    if len(hand) % groupSize != 0:
        return False
 
    freq = Counter(hand)
 
    for card in sorted(freq):
        n = freq[card]
        if n > 0:
            for i in range(groupSize):
                if freq[card + i] < n:
                    return False
                freq[card + i] -= n
 
    return True

var isNStraightHand = function(hand, groupSize) {
    if (hand.length % groupSize !== 0) return false;
 
    const freq = new Map();
    for (const card of hand) {
        freq.set(card, (freq.get(card) || 0) + 1);
    }
 
    const sortedCards = [...freq.keys()].sort((a, b) => a - b);
 
    for (const card of sortedCards) {
        const n = freq.get(card);
        if (n > 0) {
            for (let i = 0; i < groupSize; i++) {
                const count = freq.get(card + i) || 0;
                if (count < n) return false;
                freq.set(card + i, count - n);
            }
        }
    }
 
    return true;
};

Time: O(n log n) — sorting unique values dominates; the inner loop totals O(n) across all cards. Space: O(n) — frequency map stores at most n unique values.

Common Mistakes#

• Missing the divisibility check: len(hand) % groupSize != 0 makes the answer immediately false. Always check this first.
• Processing in unsorted order: If you process in arbitrary order, you may try to form groups from a large card while a smaller card (with no left neighbour) is stranded.
• KeyError on missing keys: Use freq.get(card + i, 0) in Python or check existence in JavaScript. A missing key means the consecutive sequence is broken — return false.
• Decrementing below zero: Check freq[card + i] < n before subtracting, not after.
• Integer overflow: Card values can reach 10^9; card + groupSize can reach 10^9 + groupSize. In Python this is not an issue; in Java and C++ use long.

Interview Tips#

• State the greedy argument before coding: "We must use the smallest available card now."
• Mention the O(n log n) sort and why Java's TreeMap avoids it.
• Note that LC 846 and LC 1296 are identical problems — recognising this saves time in interviews.
• Bring up the priority queue alternative: push all cards into a min-heap, pop and consume groups in order.

Follow-up Questions#

• What if groupSize is 1? Every arrangement works — return true as long as hand is non-empty.
• What if cards can appear up to 10^9 times? Batch processing by frequency already handles arbitrarily large frequencies.
• How does this transfer to "Task Scheduler" (LC 621)? Same greedy principle: always schedule the most frequent remaining task.
• Can you solve this with a priority queue instead of a sorted map? Yes — push (card, freq) pairs into a min-heap and consume groups in order. Same O(n log n) complexity.
• What is the connection to "Split Array into Consecutive Subsequences" (LC 659)? That problem requires groups of length at least 3 and uses a "needed" map to greedily extend existing groups.

Key Takeaways#

• Hand of Straights (LC 846) and Divide Array in Sets of K Consecutive Numbers (LC 1296) are identical problems.
• Check len(hand) % groupSize != 0 first — this is an immediate disqualifier.
• The greedy rule is: always start the next group from the smallest unconsumed card.
• Processing in batches of freq[card] is the key efficiency: all copies of a card must start their own group simultaneously.
• Use a sorted frequency map (sorted Counter or TreeMap) to ensure you process cards in ascending order.
• Time O(n log n) due to the sort; space O(n) for the frequency map.
• The same pattern (sorted greedy consumption) appears in task scheduling, interval merging, and partition problems across FAANG interviews.