## [846\. Hand of Straights](https://leetcode.com/problems/hand-of-straights/)

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`

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        int n = hand.size();
        if(n % groupSize) return false;

        // 使用 TreeMap 計算每個數字的頻率
        // TreeMap 裡面的 key 會從小到大排列
        map<int, int> freq;
        for(auto h : hand) ++freq[h];

        while(!freq.empty()) {
            // TreeMap 的第一個數字，也就是陣列裡最小的數字
            int first = freq.begin()->first;

            // 從 first 當作起始點，遞增到 < first + groupSize
            // 也就是遞增到每個 group 的最大值
            for(int i = first; i < first + groupSize; ++i){

                // 如果 i 不存在 freq 裡的話，代表這個數字已經被其他 group 用完了
                if(!freq.count(i)) {
                    return false;
                }
                
                // 如果 i 存在在 freq 裡的話，頻率減一
                --freq[i];
                
                // 頻率扣到為 0 的話，刪除這個 key
                if(freq[i] == 0) {
                    freq.erase(i);
                }
            }
        }
        return true;                
    }
};

:::success
- 時間複雜度：$O(n \cdot \log n)$
- 空間複雜度：$O(n)$
:::