Hand of Straights

Medium Subject: Greedy

Time Complexity

O(N log N)

Space Complexity

O(N)

Problem Description

Problem Statement

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true

Optimal Solution

Python

Approach: Hash Map Greedy

Count frequencies of each card using a hash map. Sort the unique cards. For each card, if it still has a count > 0, try to form a group starting with that card by decrementing counts for the next groupSize - 1 consecutive cards. If any card is missing, return false.

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

        count = Counter(hand)
        sorted_keys = sorted(count.keys())

        for key in sorted_keys:
            if count[key] > 0:
                freq = count[key]
                for i in range(1, groupSize):
                    if count[key + i] < freq:
                        return False
                    count[key + i] -= freq
        return True