# 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:

| Rule | Meaning |
|---|---|
| Group size | Every group has exactly `groupSize` cards |
| Consecutive values | Cards in each group are consecutive |
| Use all cards | Every card must be used exactly once |

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

| Item | Meaning |
|---|---|
| Input | `hand` and `groupSize` |
| Output | `True` if the cards can be grouped, otherwise `False` |
| Card reuse | Not allowed |
| Required group | Consecutive values of length `groupSize` |

Function shape:

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

## Examples

Example 1:

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

We can form:

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

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

So the answer is:

```python
True
```

Example 2:

```python
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:

```python
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:

```python
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:

```python
[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:

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

Counts:

```python
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:

```python
[1, 2, 3]
```

Subtract one from `1`, `2`, and `3`.

Counts become:

```python
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:

```python
[2, 3, 4]
```

Subtract one from `2`, `3`, and `4`.

Counts become:

```python
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:

```python
[6, 7, 8]
```

After subtracting, all counts are zero.

Return:

```python
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:

```python
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:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m log m + m * groupSize)` | Count cards, sort distinct values, subtract groups |
| Space | `O(m)` | Store card frequencies |

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

## Implementation

```python
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:

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

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

Then count card frequencies:

```python
count = Counter(hand)
```

Process starting values in increasing order:

```python
for start in sorted(count):
```

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

```python
copies = count[start]
```

For each required consecutive value, subtract those copies:

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

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

```python
if count[value] < 0:
    return False
```

If all forced groups are formed successfully, return `True`.

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms multiple consecutive groups |
| Not divisible | Confirms early failure |
| `groupSize = 1` | Every card forms a valid group |
| Pairs of consecutive groups | Confirms small group size |
| Duplicate full groups | Confirms multiple groups can start at same value |
| Missing duplicate card | Confirms frequency shortage is detected |