846. Hand of Straights

https://leetcode.com/problems/hand-of-straights/description/

Level: Medium

My Initial Solution

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        hand.sort()
        group_count = 0
        last_group_num = 0
        while len(hand) > 0:
            idx = 0
            while group_count < groupSize:
                if group_count == 0:
                    last_group_num = hand.pop(0)
                    group_count += 1
                else:
                    if idx == len(hand):
                        return False
                    if hand[idx] > last_group_num + 1:
                        return False
                    elif hand[idx] == last_group_num:
                        idx += 1
                    elif hand[idx] == last_group_num + 1:
                        group_count += 1
                        last_group_num = hand.pop(idx)
                    else:
                        print("this should not happen as hand is sorted")
                        return False
            group_count = 0



        return True

Solution 2

$\mathcal{O}(N\log N)$

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        freq = Counter(hand)
        min_heap = list(freq.keys())
        heapq.heapify(min_heap)
        while len(min_heap) > 0:
            smallest = min_heap[0]
            for i in range(smallest, smallest + groupSize):
                if freq[i] > 0:
                    freq[i] -= 1
                else:
                    return False
                if freq[i] == 0:
                    if i != heapq.heappop(min_heap):
                        # if there current card is now empty, and if it is not the smallest card, then it is not possible to form a group
                        return False
        return True

Solution 3

$\mathcal{O}(N)$

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        # Counter to store the count of each card value
        card_count = Counter(hand)

        for card in hand:
            start_card = card
            # Find the start of the potential straight sequence
            while card_count[start_card - 1]:
                start_card -= 1

            # Process the sequence starting from start_card
            while start_card <= card:
                while card_count[start_card]:
                    # Check if we can form a consecutive sequence
                    # of groupSize cards
                    for next_card in range(start_card, start_card + groupSize):
                        if not card_count[next_card]:
                            return False
                        card_count[next_card] -= 1
                start_card += 1

        return True