LC 846 - Hand of Straights

Question

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 1:

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]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false

Explanation: Alice’s hand can not be rearranged into groups of 4.

Constraints:

• 1 <= hand.length <= 104
• 0 <= hand[i] <= 109
• 1 <= groupSize <= hand.length

Note: This question is the same as 1296. Divide Array in Sets of K Consecutive Numbers

Links

Question here and solution here

Solution

concept

We will use a hashmap to keep track the frequency count We will also use a heap to keep track the smallest element, this element is the start of the sequence in each group

As we forming the sequence, we will decrement the count hashmap. Whenever there is number’s count reach 0, we will have to pop from the heap.

This question’s design is such that if we ever pop a number that is not the minimum in the min heap, we should return False. This is because there are still smaller number left in the heap, which will be used for other group, but if you pop the (larger) element this will create a hole in the other sequence, which will make the algorithm fail.

Note that we do not need to delete the number from the count dict when it reach 0. This is because if it ever reach 0 somewhere in the algorithm, it will be forced to pop from the heap and we can check the sequence validity from there.

code

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        """
        Greedy algo with min heap

        time complexity: O(nlogn)
        space complexity: O(n)

        keep track of the freq count of each number -> to use to construct number block
        keep track of the smallest element in the heap -> to select the smallest 
        """
        if len(hand) % groupSize:
            return False
        
        # freq count for each num
        count = {}
        for num in hand:
            if num in count:
                count[num] += 1
            else:
                count[num] = 1

        min_heap = list(count.keys())
        heapq.heapify(min_heap)
        
        while min_heap:
            # the first element in each block of numbers
            first = min_heap[0]
            # for one block of number
            # pop smallest if the freq count is 0
            for i in range(first, first + groupSize):
                if i not in count:
                    return False
                count[i] -= 1
                # edge case where the element we removed is 0 but it is not the smallest element in the heap
                # this will lead to a hole in the next number block if pop this number
                if count[i] == 0:
                    if i != min_heap[0]:
                        return False
                    heapq.heappop(min_heap)
        return True

Complexity

time: $O(n \log n)$
space: $O(n)$