Problem of The Day: Hand of Straights

Problem Statement

Intuition

My first thought was to use a sorting or priority queue approach since I need to form consecutive groups of cards. Using a min-heap (priority queue) will allow me to efficiently access and remove the smallest card, which is crucial for checking consecutive sequences.

Approach

1. Initialize a Min-Heap: I start by pushing all cards from the hand into a min-heap. This ensures that I can always access the smallest remaining card efficiently.
2. Process the Min-Heap: I use a while loop to process cards from the heap until it’s empty.
   • Get the First Card: I pop the smallest card from the heap as the start of a potential group.
   • Form the Group: I then try to form a group of groupSize cards starting from this card. I maintain a count of the cards in the current group and use another list (curr) to temporarily store cards that cannot be part of the current sequence.
   • Check Consecutive Cards: If the next card from the heap is consecutive to the previous card, I include it in the current group. Otherwise, I put it in the curr list.
3. Restore Non-Consecutive Cards: After attempting to form a group, I push back all the cards in curr to the heap since they weren’t used in the current group.
4. Final Check: If at any point I cannot form a complete group of groupSize cards, I return False. If I process all cards successfully, I return True.

Complexity

• Time complexity:

  • The time complexity is (O(n \log n)) where (n) is the number of cards. This is due to the heap operations which are (O(\log n)) for each of the (n) cards.

• Space complexity:

  • The space complexity is (O(n)) due to the space required for the min-heap and the temporary list curr.

Code

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        min_heap = []
        for card in hand:
            heapq.heappush(min_heap, card)

        while min_heap:
            prev = heapq.heappop(min_heap)
            curr = []
            count = 1
            while count < groupSize:
                if not min_heap:
                    return False
                next_card = heapq.heappop(min_heap)
                if prev + 1 == next_card:
                    prev = next_card
                    count += 1
                else:
                    curr.append(next_card)

            while curr:
                heapq.heappush(min_heap, curr.pop())

        return True

Editorial

Approach 2: Rerverse Decrement

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

• Time: O(n)
• Space: O(n)