LeetCode 846: Hand of Straights

Problem Restatement

We are given an integer array hand, where each value is written on one card.

We are also given an integer groupSize.

We need to decide whether all cards can be rearranged into groups such that:

Return True if this is possible. Otherwise, return False.

The problem also notes that it is the same as LeetCode 1296, Divide Array in Sets of K Consecutive Numbers.

Input and Output

Function shape:

class Solution:
    def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
        ...

Examples

Example 1:

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

We can form:

[1, 2, 3]
[2, 3, 4]
[6, 7, 8]

All groups have size 3, and all groups are consecutive.

So the answer is:

True

Example 2:

hand = [1, 2, 3, 4, 5]
groupSize = 4

There are 5 cards.

We cannot split 5 cards into groups of size 4.

So the answer is:

False

First Thought: Try to Build Groups

The direct idea is to repeatedly build one consecutive group at a time.

If the smallest remaining card is x, then it must start a group.

It cannot appear in the middle of a group, because that would require cards smaller than x, and no smaller remaining card exists.

So after choosing x, we must also have:

x + 1, x + 2, ..., x + groupSize - 1

available.

This gives a greedy solution.

Key Insight

Always start groups from the smallest remaining card.

For example, if the smallest remaining card is 2 and groupSize = 3, the only possible group containing this card is:

[2, 3, 4]

If 3 or 4 is missing, there is no valid arrangement.

This greedy choice is forced, not just convenient.

Algorithm

1. If the number of cards is not divisible by groupSize, return False.
2. Count how many times each card value appears.
3. Process card values in sorted order.
4. If card start still has count c > 0, then we must create c groups starting at start.
5. For each value from start to start + groupSize - 1, subtract c.
6. If any count becomes negative, return False.
7. If all groups are formed, return True.

Walkthrough

Use:

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

Counts:

1: 1
2: 2
3: 2
4: 1
6: 1
7: 1
8: 1

Start with card 1.

Its count is 1, so we need one group:

[1, 2, 3]

Subtract one from 1, 2, and 3.

Counts become:

1: 0
2: 1
3: 1
4: 1
6: 1
7: 1
8: 1

Next card with positive count is 2.

Its count is 1, so we need one group:

[2, 3, 4]

Subtract one from 2, 3, and 4.

Counts become:

1: 0
2: 0
3: 0
4: 0
6: 1
7: 1
8: 1

Next card with positive count is 6.

Its group must be:

[6, 7, 8]

After subtracting, all counts are zero.

Return:

True

Correctness

If the total number of cards is not divisible by groupSize, then using all cards in equal-sized groups is impossible. Returning False is correct.

Now suppose the smallest remaining card is x.

In any valid grouping, this card must belong to some group of consecutive cards. Since there is no smaller remaining card, x cannot be the second, third, or later card in that group. Therefore, x must be the first card of its group.

So every remaining copy of x forces one group starting at x.

For each forced group, the cards:

x, x + 1, ..., x + groupSize - 1

must exist. If any required card is missing, no valid grouping can exist.

The algorithm applies exactly this forced choice from smallest to largest. It never uses a card in a way that could block a better solution, because the smallest remaining card has no alternative position.

Therefore, if the algorithm fails, no valid grouping exists. If it finishes, it has partitioned all cards into valid consecutive groups.

Complexity

Let:

n = len(hand)
m = number of distinct card values

A simpler implementation that sorts the whole hand can be O(n log n).

Implementation

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        count = Counter(hand)

        for start in sorted(count):
            copies = count[start]

            if copies == 0:
                continue

            for value in range(start, start + groupSize):
                count[value] -= copies

                if count[value] < 0:
                    return False

        return True

Code Explanation

First, check divisibility:

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

If cards cannot be evenly split into groups, no arrangement can work.

Then count card frequencies:

count = Counter(hand)

Process starting values in increasing order:

for start in sorted(count):

If start still has copies remaining, those copies must each begin a group:

copies = count[start]

For each required consecutive value, subtract those copies:

for value in range(start, start + groupSize):
    count[value] -= copies

If a required value does not have enough cards, its count becomes negative:

if count[value] < 0:
    return False

If all forced groups are formed successfully, return True.

Testing

def run_tests():
    s = Solution()

    assert s.isNStraightHand(
        [1, 2, 3, 6, 2, 3, 4, 7, 8],
        3,
    ) is True

    assert s.isNStraightHand(
        [1, 2, 3, 4, 5],
        4,
    ) is False

    assert s.isNStraightHand(
        [1, 2, 3, 4],
        1,
    ) is True

    assert s.isNStraightHand(
        [1, 2, 3, 4, 5, 6],
        2,
    ) is True

    assert s.isNStraightHand(
        [1, 1, 2, 2, 3, 3],
        3,
    ) is True

    assert s.isNStraightHand(
        [1, 1, 2, 2, 3, 4],
        3,
    ) is False

    print("all tests passed")

run_tests()

Test meaning: