Hand of Straights

Difficulty: Medium Source: NeetCode

Problem

Alice has a hand of cards given as an integer array hand. She wants to rearrange the cards into groups of size groupSize consecutive cards. Return true if she can, false otherwise.

Example 1: 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]

Example 2: Input: hand = [1,2,3,4,5], groupSize = 4 Output: false

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Hash maps — counting card frequencies
• Greedy algorithms — always process the smallest available card
• Sorted iteration — using SortedDict or sorted keys

1. Brute Force

Intuition

Repeatedly sort the hand and find the smallest card. Try to form a consecutive group starting from that card. Remove the used cards and repeat until either all cards are used (return True) or a group can’t be formed (return False).

Algorithm

1. While hand is non-empty:
   • Sort hand.
   • Take the smallest card start = hand[0].
   • For i from start to start + groupSize - 1:
     • If i is not in hand, return False.
     • Remove one occurrence of i.
2. Return True.

Solution

def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize != 0:
        return False

    hand_list = list(hand)

    while hand_list:
        hand_list.sort()
        start = hand_list[0]
        for card in range(start, start + groupSize):
            if card not in hand_list:
                return False
            hand_list.remove(card)

    return True


print(isNStraightHand([1, 2, 3, 6, 2, 3, 4, 7, 8], 3))  # True
print(isNStraightHand([1, 2, 3, 4, 5], 4))               # False
print(isNStraightHand([1, 1, 2, 2, 3, 3], 3))            # True

Complexity

• Time: O(n² log n) — sort and list.remove per group
• Space: O(n)

2. Greedy with Ordered Frequency Map

Intuition

Always process groups starting from the smallest available card. Use a frequency counter. Iterate the sorted unique card values. For the smallest card with count > 0, try to form count groups starting at that card (each group uses cards card, card+1, ..., card+groupSize-1). If any of those successor cards don’t have enough copies, return False. This greedy is optimal because you must eventually use the smallest card, and it can only be the start of a group.

Algorithm

1. If len(hand) % groupSize != 0, return False.
2. Count frequencies: count = Counter(hand).
3. Sort the unique cards.
4. For each unique card c (in sorted order):
   • If count[c] == 0, skip.
   • n = count[c] — need to start n groups here.
   • For i from 0 to groupSize - 1:
     • If count[c + i] < n, return False.
     • count[c + i] -= n.
5. Return True.

Solution

from collections import Counter

def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize != 0:
        return False

    count = Counter(hand)
    sorted_keys = sorted(count.keys())

    for c in sorted_keys:
        if count[c] == 0:
            continue
        n = count[c]  # how many groups start at c
        for i in range(groupSize):
            if count[c + i] < n:
                return False
            count[c + i] -= n

    return True


print(isNStraightHand([1, 2, 3, 6, 2, 3, 4, 7, 8], 3))  # True
print(isNStraightHand([1, 2, 3, 4, 5], 4))               # False
print(isNStraightHand([1, 1, 2, 2, 3, 3], 3))            # True
print(isNStraightHand([1], 1))                            # True
print(isNStraightHand([1, 2, 3, 4, 5, 6], 3))            # True

Complexity

• Time: O(n log n) — sorting the unique keys
• Space: O(n) — frequency map

Common Pitfalls

Not checking divisibility first. If len(hand) % groupSize != 0, it’s immediately impossible — no need to even look at the cards.

Processing cards in wrong order. You must process in sorted order. If you pick a random card to start a group, you might skip over cards that can only be group starters.

Accessing count[c + i] when that key doesn’t exist. Use Counter which defaults missing keys to 0, or check if c + i not in count explicitly. If count[c + i] is less than n, the group can’t be formed.