Hand of Straights
Problem Statement
You are given an integer array hand
where hand[i]
is the value written on the ith
card and an integer groupSize
.
You want to rearrange the cards into groups so that each group is of size groupSize
, and card values are consecutively increasing by 1
.
Return true
if it’s possible to rearrange the cards in this way, otherwise, return false
.
Example 1:
Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4
Output: true
Explanation: The cards can be rearranged as [1,2,3,4]
and [2,3,4,5]
.
Example 2:
Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4
Output: false
Explanation: The closest we can get is [1,2,3,4]
and [3,5,6,7]
, but the cards in the second group are not consecutive.
Constraints:
1 <= len(hand) <= 1000
0 <= hand[i] <= 1000
1 <= groupSize <= len(hand)
Recommended Time and Space Complexity
You should aim for a solution with O(n log n)
time and O(n)
space, where n
is the length of the input array.
Hint 1
Consider using a hash map to store the frequency of each number in the input array.
Hint 2
You can sort the array and then iterate through it, checking if consecutive numbers exist in the required quantity.
Hint 3
Think about using a heap to efficiently find the smallest number and then check for consecutive numbers.
Solution
Sorting
from collections import Counter
def is_n_straight_hand_sorting(hand, group_size): if len(hand) % group_size: return False count = Counter(hand) hand.sort() for num in hand: if count[num]: for i in range(num, num + group_size): if not count[i]: return False count[i] -= 1 return True
Time complexity: O(n log n)
Space complexity: O(n)
Heap
import heapqfrom collections import Counter
def is_n_straight_hand_heap(hand, group_size): if len(hand) % group_size: return False
count = Counter(hand) min_heap = list(count.keys()) heapq.heapify(min_heap)
while min_heap: first = min_heap[0] for i in range(first, first + group_size): if i not in count: return False count[i] -= 1 if count[i] == 0: if i != min_heap[0]: return False heapq.heappop(min_heap) return True
Time complexity: O(n log n)
Space complexity: O(n)
Ordered Map (Counter + Deque)
from collections import Counter, deque
def is_n_straight_hand_ordered_map(hand, group_size): if len(hand) % group_size != 0: return False
count = Counter(hand) queue = deque() last_num, open_groups = -1, 0
for num in sorted(count): if ((open_groups > 0 and num > last_num + 1) or open_groups > count[num] ): return False
queue.append(count[num] - open_groups) last_num = num open_groups = count[num]
if len(queue) == group_size: open_groups -= queue.popleft()
return open_groups == 0
Time complexity: O(n log n)
Space complexity: O(n)
Hash Map
from collections import Counter
def is_n_straight_hand_hash_map(hand, group_size): if len(hand) % group_size != 0: return False count = Counter(hand) for num in hand: start = num while count[start - 1]: start -= 1 while start <= num: while count[start]: for i in range(start, start + group_size): if not count[i]: return False count[i] -= 1 start += 1 return True
Time complexity: O(n)
Space complexity: O(n)