Hand of Straights — LeetCode 846 Python Solution

The problem

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, or false otherwise.

Example

Input

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Output

true

Explanation

Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Python solution

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        cnt = Counter(hand)
        for x in sorted(hand):
            if cnt[x]:
                for y in range(x, x + groupSize):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 846. Hand of Straights is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems