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)

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 heapq
from 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)