# Hand of Straights
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/hand-of-straights)
Canonical: https://scaleengineer.com/dsa/problems/hand-of-straights
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
Alice has some number of cards and she wants to rearrange the cards 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 written on the `ith` card and an integer `groupSize`, return `true` if she can rearrange the cards, or `false` otherwise.

**Example 1:**

**Input:** hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
**Output:** true
**Explanation:** Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

**Example 2:**

**Input:** hand = [1,2,3,4,5], groupSize = 4
**Output:** false
**Explanation:** Alice's hand can not be rearranged into groups of 4.

**Constraints:**

* `1 <= hand.length <= 104`
* `0 <= hand[i] <= 109`
* `1 <= groupSize <= hand.length`

**Note:** This question is the same as 1296: <https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/>

# Approaches
## Brute Force with Sorting and Linear Scan
This approach first sorts the hand to make finding consecutive cards easier. It then iterates through the sorted hand, and for each card not yet used, it tries to form a new group of `groupSize` consecutive cards by scanning the rest of the array. A boolean array is used to keep track of cards that have been placed into a group.
**Time:** O(N^2). Sorting the array takes O(N log N). The main loop iterates through N elements. Inside, for each potential group start, we might scan a large portion of the array up to `groupSize` times. This results in a time complexity dominated by the nested search, which is approximately O((N/groupSize) * groupSize * N) = O(N^2). · **Space:** O(N), where N is the number of cards in the hand. This space is used for the `used` boolean array.
**Pros:** Conceptually simple and easy to understand.; It's a direct simulation of the grouping process.
**Cons:** Highly inefficient due to the nested loops and repeated linear scanning.; Will likely result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) {
            return false;
        }

        Arrays.sort(hand);
        boolean[] used = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            
            // This card starts a new group
            int lastCard = hand[i];
            used[i] = true;
            int cardsInGroup = 1;
            
            // Find the rest of the group
            int searchIdx = i + 1;
            while (cardsInGroup < groupSize) {
                int nextCardNeeded = lastCard + 1;
                int foundIdx = -1;
                // Linearly scan for the next card
                for (int j = searchIdx; j < n; j++) {
                    if (!used[j] && hand[j] == nextCardNeeded) {
                        foundIdx = j;
                        break;
                    }
                }

                if (foundIdx != -1) {
                    used[foundIdx] = true;
                    lastCard = hand[foundIdx];
                    cardsInGroup++;
                    searchIdx = foundIdx + 1; // Optimization: start next search after the found card
                } else {
                    // Could not find the next consecutive card
                    return false;
                }
            }
        }

        return true;
    }
}
```
### Algorithm
*   First, perform a basic check: if the total number of cards `hand.length` is not divisible by `groupSize`, it's impossible to form the required groups, so return `false`.
*   Sort the `hand` array in ascending order. This makes it easier to find consecutive cards.
*   Create a boolean array `used` of the same size as `hand`, initialized to `false`, to keep track of which cards have been assigned to a group.
*   Iterate through the sorted `hand` from left to right. For each card `hand[i]`:
    *   If the card is already used (`used[i]` is `true`), skip it.
    *   If it's not used, treat it as the starting card of a new group.
    *   Mark `used[i]` as `true`.
    *   Now, search for the next `groupSize - 1` consecutive cards (`hand[i] + 1`, `hand[i] + 2`, etc.) in the rest of the array.
    *   For each required consecutive card, perform a linear scan from the current position onwards to find an available (unused) card with the correct value.
    *   If a required card is found, mark it as used and continue searching for the next one in the sequence.
    *   If at any point a required consecutive card cannot be found, it means a valid group cannot be formed from the current starting card. Return `false`.
*   If the entire `hand` array is traversed and all cards are successfully grouped, return `true`.

## Using a HashMap and Sorting Keys
This approach improves upon the brute-force method by using a hash map to count the frequency of each card, which avoids the costly linear scans. After counting, it sorts the unique card numbers and iterates through them to form groups. For each starting card, it checks if enough consecutive cards exist and updates their counts in the map.
**Time:** O(N + U log U + U * groupSize), where N is the number of cards and U is the number of unique cards. Building the map is O(N). Sorting the U keys is O(U log U). Iterating through U keys and for each, checking `groupSize` cards is O(U * groupSize). In the worst case (U=N), this is O(N log N + N * groupSize). · **Space:** O(U), where U is the number of unique cards. In the worst case, U can be N, so O(N). This space is for the `HashMap` and the list of keys.
**Pros:** Much more efficient than the brute-force approach by avoiding repeated scans of the array.; Handles duplicate cards efficiently through frequency counting.
**Cons:** The performance can degrade if `groupSize` is large, as the complexity has a `U * groupSize` term.; Requires an explicit sorting step after building the map.
### Explanation
```java
import java.util.Collections;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }

        Map<Integer, Integer> cardCounts = new HashMap<>();
        for (int card : hand) {
            cardCounts.put(card, cardCounts.getOrDefault(card, 0) + 1);
        }

        List<Integer> sortedKeys = new ArrayList<>(cardCounts.keySet());
        Collections.sort(sortedKeys);

        for (int key : sortedKeys) {
            int count = cardCounts.get(key);
            if (count > 0) { // If this card is a potential start of a new group(s)
                for (int i = 0; i < groupSize; i++) {
                    int currentCard = key + i;
                    if (cardCounts.getOrDefault(currentCard, 0) < count) {
                        return false;
                    }
                    cardCounts.put(currentCard, cardCounts.get(currentCard) - count);
                }
            }
        }

        return true;
    }
}
```
### Algorithm
*   First, check if `hand.length` is divisible by `groupSize`. If not, return `false`.
*   Create a `HashMap` to store the frequency of each card. Iterate through the `hand` array and populate this map. For example, `map.put(card, map.getOrDefault(card, 0) + 1)`.
*   Extract the unique card numbers (the keys of the map) into a `List`.
*   Sort this list of unique keys in ascending order.
*   Iterate through the `sortedKeys` list.
*   For each `key` in the list:
    *   Get its frequency from the map: `count = cardCounts.get(key)`.
    *   If `count` is 0, it means this card has already been fully used in groups starting with smaller cards, so we can `continue` to the next key.
    *   If `count > 0`, it signifies that we must form `count` new groups starting with this `key`.
    *   To form these groups, we check for the availability of the next `groupSize - 1` consecutive cards. Loop from `i = 0` to `groupSize - 1`:
        *   Let `currentCard = key + i`.
        *   Check if the map has enough copies of `currentCard`. If `cardCounts.getOrDefault(currentCard, 0) < count`, return `false`.
        *   If available, 'use' these cards by decrementing their counts in the map: `cardCounts.put(currentCard, cardCounts.get(currentCard) - count)`.
*   If the loop completes without returning `false`, it means all cards were successfully grouped. Return `true`.

## Optimal Approach with a Sorted Map (TreeMap)
This is the most efficient approach. It uses a `TreeMap`, which is a sorted map, to store card frequencies. This combines the counting and sorting steps, allowing us to greedily form groups starting from the smallest available card without a separate sorting phase. By always processing the smallest card first, we ensure that if a solution exists, this greedy strategy will find it.
**Time:** O(N log U), where N is the number of cards and U is the number of unique cards. Building the `TreeMap` takes O(N log U) as each of the N insertions takes O(log U) time. The processing loop consumes each card exactly once. Each consumption involves map operations (get, put, remove) which take O(log U) time. Thus, the total processing time is also bounded by O(N log U). In the worst case where U=N, the complexity is O(N log N). · **Space:** O(U), where U is the number of unique cards. In the worst case, U can be N, so O(N). This space is for the `TreeMap`.
**Pros:** Most efficient and robust solution.; The greedy strategy is guaranteed to work because we always start with the smallest available card.; The `TreeMap` handles sorting implicitly, leading to cleaner code and better overall time complexity.
**Cons:** The underlying data structure (`TreeMap`, a balanced binary search tree) is slightly more complex than a `HashMap`.
### Explanation
```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }

        // TreeMap stores keys in sorted order
        Map<Integer, Integer> cardCounts = new TreeMap<>();
        for (int card : hand) {
            cardCounts.put(card, cardCounts.getOrDefault(card, 0) + 1);
        }

        while (!cardCounts.isEmpty()) {
            // Get the smallest card number available
            int startCard = cardCounts.keySet().iterator().next(); // or ((TreeMap<Integer, Integer>) cardCounts).firstKey();
            int count = cardCounts.get(startCard);

            // We need to form 'count' groups starting with 'startCard'.
            // Check if we have enough consecutive cards for all 'count' groups.
            for (int i = 0; i < groupSize; i++) {
                int currentCard = startCard + i;
                if (cardCounts.getOrDefault(currentCard, 0) < count) {
                    return false;
                }
                
                // Use up 'count' cards of value 'currentCard'
                cardCounts.put(currentCard, cardCounts.get(currentCard) - count);
                
                // If the count of a card becomes zero, remove it from the map
                if (cardCounts.get(currentCard) == 0) {
                    cardCounts.remove(currentCard);
                }
            }
        }

        return true;
    }
}
```
### Algorithm
*   As with other approaches, first check if `hand.length % groupSize != 0` and return `false` if true.
*   Create a `TreeMap<Integer, Integer>` to store the frequency of each card. A `TreeMap` is a sorted map, so it will automatically keep the card numbers (keys) in ascending order.
*   Populate the `TreeMap` by iterating through the `hand` array.
*   Start a loop that continues as long as the `TreeMap` is not empty.
*   Inside the loop, get the smallest card currently available. This is the greedy choice for the start of a new group. This can be done via `map.firstKey()`.
*   Get the frequency of this starting card, `startCard`. Let this be `count`.
*   This `count` tells us we need to form `count` groups starting with `startCard`.
*   Now, verify and consume the cards for these `count` groups. Iterate from `i = 0` to `groupSize - 1`:
    *   Let `currentCard = startCard + i`.
    *   Check if the map contains `currentCard` and if its frequency is at least `count`. If `cardCounts.getOrDefault(currentCard, 0) < count`, it's impossible to form the groups, so return `false`.
    *   If the check passes, update the frequency of `currentCard` by subtracting `count`: `cardCounts.put(currentCard, cardCounts.get(currentCard) - count)`.
    *   If the new frequency of `currentCard` becomes 0, remove it from the map entirely using `cardCounts.remove(currentCard)`. This is crucial for efficiency and for the loop's termination condition.
*   If the `while` loop finishes (meaning the map becomes empty), all cards have been successfully arranged into groups. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isNStraightHand(int[] hand, int groupSize) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int v : hand) {
      cnt.put(v, cnt.getOrDefault(v, 0) + 1);
    }
    Arrays.sort(hand);
    for (int v : hand) {
      if (cnt.containsKey(v)) {
        for (int x = v; x < v + groupSize; ++x) {
          if (!cnt.containsKey(x)) {
            return false;
          }
          cnt.put(x, cnt.get(x) - 1);
          if (cnt.get(x) == 0) {
            cnt.remove(x);
          }
        }
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isNStraightHand(vector<int> &hand, int groupSize) {
    unordered_map<int, int> cnt;
    for (int &v : hand)
      ++cnt[v];
    sort(hand.begin(), hand.end());
    for (int &v : hand) {
      if (cnt.count(v)) {
        for (int x = v; x < v + groupSize; ++x) {
          if (!cnt.count(x)) {
            return false;
          }
          if (--cnt[x] == 0) {
            cnt.erase(x);
          }
        }
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: cnt = Counter(hand) for v in sorted(hand): if cnt[v]: for x in range(v, v + groupSize): if cnt[x] == 0: return False cnt[x] -= 1 if cnt[x] == 0: cnt . pop(x) return True

```