Hand of Straights LeetCode solution in Python

1
# Runtime: 304 ms (Top 61.38%) | Memory: 15.7 MB (Top 75.38%)
2

3
#####################################################################################################################
4
# Problem: Hand of Straights
5
# Solution : Hash Table, Min Heap
6
# Time Complexity : O(n logn)
7
# Space Complexity : O(n)
8
#####################################################################################################################
9

10

11
class Solution:
12
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
13
        if len(hand) % groupSize:
14
            return False
15

16
        freq = collections.defaultdict(int)
17

18
        for num in hand:
19
            freq[num] += 1
20

21
        min_heap = list(freq.keys())
22
        heapq.heapify(min_heap)
23

24
        while min_heap:
25
            smallest = min_heap[0]
26
            for num in range(smallest, smallest + groupSize):
27
                if num not in freq:
28
                    return False
29
                freq[num] -= 1
30

31
                if freq[num] == 0:
32
                    if num != min_heap[0]:
33
                        return False
34
                    heapq.heappop(min_heap)
35
        return True