## Question

###### tags: `Greedy` `Medium`

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

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {number[]} hand
 * @param {number} groupSize
 * @return {boolean}
 */

// Time: O(n^2), Space: O(n)

var isNStraightHand = function(hand, groupSize) {
    if (hand.length % groupSize !== 0) return false;
    hand.sort((a, b) => a - b);
    let count = 0;
    let consecutiveVal = 0;
    let pointer = 0;
    while(count < hand.length){ // O(n)
        if(count % groupSize === 0){
            if(hand[pointer] !== -1){
                consecutiveVal = hand[pointer];
                hand[pointer] = -1;
                count++;
            }else{
                pointer++;
            }
        }else{
            const index = hand.indexOf(consecutiveVal + 1) // O(n)
            if(index === -1) return false
            
            consecutiveVal = hand[index];
            hand[index] = -1;
            count++;
        }
    }
    return true;
};

:::

<hr/>

### Sol
:::spoiler Code

var isNStraightHand = function(hand, groupSize) {
    if(hand.length % groupSize > 0) return false;
    hand.sort((a,b)=>a-b)
    const countMap = {}
    for(let i =0; i< hand.length; i++){
        countMap[hand[i]] = (countMap[hand[i]] || 0) +1
    }
    for(let i =0; i< hand.length-1; i++){
        if( countMap[hand[i]] > 0){ // 2
            // Try to form a group starting from this card, 2, 3, 4
            for(let j= hand[i]; j< hand[i] + groupSize;j++){
                if(countMap[j] > 0){
                    countMap[j] = countMap[j] - 1
                }else{
                    return false;
                }
            }
        }
    }
    return true;
};

:::

<hr/>

### 東

:::spoiler Code

// Time O(m*n) | Space O(m) - m is length of hand, n is groupSize
var isNStraightHand = function(hand, groupSize) {
    hand.sort((a, b) => a - b);
    const cardMap = new Map();
    for(const card of hand) {
        if(cardMap.has(card)) {
            cardMap.set(card, cardMap.get(card) + 1);
        } else {
            cardMap.set(card, 1);
        }
    }

    const mapIter = cardMap.keys();
    let startCard = null;
    while(true) {
        startCard = mapIter.next().value;
        if(startCard === undefined) break;
        
        const startCardCount = cardMap.get(startCard);
        if(startCardCount === 0) continue;
        for(let i = 0; i < groupSize; i++) {
            if(!cardMap.has(startCard + i) || cardMap.get(startCard + i) < startCardCount) return false;
            cardMap.set(startCard + i, cardMap.get(startCard + i) - startCardCount);
        } 
    }

    return true;
};

:::

<hr/>

### Jessie

Time Complexity: O(n log n) due to sorting, where n is the number of cards.
Space Complexity: O(n) due to the countMap, where n is the number of cards.
:::spoiler Code

/**
 * @param {number[]} cards
 * @param {number} groupSize
 * @return {boolean}
 */
var isNStraightHand = function (cards, groupSize) {
  if (cards.length % groupSize !== 0) return false;

  cards.sort((a, b) => a - b);

  const countMap = new Map();

  //  計算每張牌的數量
  for (let card of cards) {
    countMap.set(card, (countMap.get(card) || 0) + 1);
  }

  let countRemoved = 0;
  for (let card of cards) {
    if (countRemoved === cards.length) break; //  所有牌都拿完的時候可以不用繼續跑完剩下的
    if (countMap.get(card) === 0) continue;

    //  以目前 card 為起始點按照 groupSize 檢查是否是連續的卡
    for (let i = 0; i < groupSize; i++) {
      let currentCard = card + i;

      //  沒有連續的卡, 或是連續的卡沒了
      if ([undefined, 0].includes(countMap.get(currentCard))) return false;

      //  檢查一個就拿掉一張
      countMap.set(currentCard, countMap.get(currentCard) - 1);
      countRemoved++;
    }
  }

  return true;
};

:::

<hr/>

### Howard

:::spoiler Code

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # idea: use counter and heap
        # time O(nlogn)
        # space O(n)

        # check divisible
        if len(hand) % groupSize:
            return False

        # build counter and heap
        counter = defaultdict(int)
        heap = []
        for h in hand:
            counter[h] += 1
            if counter[h] == 1:
                heapq.heappush(heap, h)

        # go through counter from start
        group_count = 0
        while group_count < len(hand) // groupSize:
            gi = 0
            current_card = heap[0]  # smallest card left
            while gi < groupSize:
                # if cannot form group consecutively, return False
                if current_card not in counter:
                    return False
                counter[current_card] -= 1
                if counter[current_card] == 0:
                    heapq.heappop(heap)
                    counter.pop(current_card)
                current_card += 1
                gi += 1
            group_count += 1
        
        return True

:::

<hr/>

### Haoyu

:::spoiler Code

/**
 * @param {number[]} hand
 * @param {number} groupSize
 * @return {boolean}
 */
var isNStraightHand = function(hand, groupSize) {
    const sorted = [...hand].sort((a, b) => a - b);
    const unsatisfiedGroupRecord = {};

    let toGroup = sorted.shift();

    while (toGroup !== undefined) {
        const targetGroup = unsatisfiedGroupRecord[toGroup]?.[0];

        const pushUnsatisfiedGroup = (index, group) => {
            if (!unsatisfiedGroupRecord[index]) (unsatisfiedGroupRecord[index] = []);
            unsatisfiedGroupRecord[index].push(group);
        };

        if (targetGroup) {
            targetGroup.push(toGroup);
            unsatisfiedGroupRecord[toGroup].shift();

            if (targetGroup.length < groupSize) pushUnsatisfiedGroup(toGroup + 1, targetGroup)
        } else {
            const newGroup = [toGroup];

            if (newGroup.length < groupSize) pushUnsatisfiedGroup(toGroup + 1, newGroup)
        };

        toGroup = sorted.shift();
    }

    return !Object.values(unsatisfiedGroupRecord).reduce((acc, value) => acc + value.length, 0);
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::