LC846. Hand of Straights

class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        """
        0. edge case  len = m *k 
        1. cnt freq 
        2. iterate sorted num,   num,num+1, .. num+W-1 freq -= cnt from the most front number 
        3. if num == 0 but val before num  != 0: return False 
        4. return True   
        tc O(MlgM+N+ M*W) M: number of uniqe val  N: len of hand
        sc O(M)  
        """
        if W == 1: return True
        if len(hand) %W != 0:
            return False 
        c = collections.Counter(hand)
        for x in sorted(c):
            if c[x] > 0 :
                for j in range(W)[::-1]:
                    c[x+j] -= c[x]
                    if c[x+j] < 0:
                        return False
        return True 

# tc O(MlgM + N )
class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        c = collections.Counter(hand)
        q = collections.deque()
        last_checked_val, opened_cnt = -1,0
        for x in sorted(c):
            # smallest number's cnt > next val    next val is not consecutive and previous value still have cnt 
            if opened_cnt > c[x] or            opened_cnt >0 and x > last_checked_val +1 :return False
            q.append(c[x]-opened_cnt)
            last_checked_val= x # mark last visited val and last visited cnt  
            opened_cnt  = c[x]  
            if len(q) == W:
                opened_cnt -= q.popleft()
        return opened_cnt == 0 

from collections import Counter
class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        if W == 0:
            return True 
        if len(hand) % W != 0:
            return False
        
        c = Counter(hand)
        while c :
            card,cnt  = c.popitem()
            c[card] = cnt
            # get smallest car for the grough where card is in 
            min_card = card
            while min_card in c:
                min_card -= 1
            min_card += 1
            
            
            cur_card = min_card
            opened = 0 
            open_start = {}
            while cur_card in c:
                cnt = c.pop(cur_card)
                if cnt < opened :
                    return False 
                open_start[cur_card] = cnt - opened 
                closed = open_start.get(cur_card-W+1,0)
                opened += open_start[cur_card] - closed 
                cur_card += 1
                
            if opened > 0:
                return False
        return True