Solutions

# Sort or use a min heap to always start the sequence with the smallest card, then check if the next groupSize-1 cards are present using a frequency map.
# greedy

from collections import defaultdict

# Min heap - O(n log n) time, O(n) space
def isNStraightHand(hand: list[int], groupSize: int) -> bool:
    import heapq
    if len(hand) % groupSize != 0:
        return False

    freq = defaultdict(int)
    for i in hand:
        freq[i] += 1

    heapq.heapify(hand)
    while hand:
        minval = heapq.heappop(hand)
        if freq[minval] == 0:
            continue

        freq[minval] -= 1
        for n in range(minval + 1, minval + groupSize):
            if freq[n] == 0:
                return False
            freq[n] -= 1
    
    return True

    
# Sorting - O(n log n) time, O(n) space
def isNStraightHand(hand: list[int], groupSize: int) -> bool:
    if len(hand) % groupSize != 0:
        return False

    # could also use: freq = Counter(hand)
    freq = defaultdict(int)
    for i in hand:
        freq[i] += 1

    hand.sort()

    for num in hand:
        if freq[num]:
            for i in range(num, num + groupSize):
                if not freq[i]:
                    return False
                freq[i] -= 1
    return True
    
# [HARD] Greedy with counter - O(n) time, O(n) space
def isNStraightHand(hand: list[int], groupSize: int) -> bool:
    if len(hand) % groupSize != 0:
        return False

    # could also use: freq = Counter(hand)
    freq = defaultdict(int)
    for i in hand:
        freq[i] += 1

    for num in hand:
        start = num

        # Find the start of the sequence
        while freq[start -1] > 0:
            start -= 1

        while start <= num:
            while freq[start] > 0:
                for i in range(start, start + groupSize):
                    if freq[i] == 0:
                        return False
                    freq[i] -= 1
            start += 1

    return True