Hand Of Straights - Leetcode Solution

The problem "Hand of Straights" on LeetCode is stated as follows:

You are given an array of integers hand representing the cards you have. Each integer in hand represents a card of the corresponding value. The value of each card ranges from 1 to W where W is the maximum value of any card in hand.

You want to rearrange the cards in the hand into groups so that each group has W cards, and no two cards of the same value are in the same group. You can rearrange the cards in any way you like, but you must rearrange all the cards.

Return true if it is possible to rearrange the cards as described, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3 Output: true Explanation: You can split the hand into [1,2,3], [2,3,4], [6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4 Output: false Explanation: There is no way to split the hand into groups of 4.

The problem can be solved using a hash map and a priority queue. The steps involved in the solution are as follows:

1. First, we count the frequency of each card using a hash map. We can do this in O(n) time complexity where n is the number of cards.

2. Next, we initialize a priority queue with the keys of the hash map. We can use a priority queue because we want to process the cards in ascending order of value.

3. Now we start processing the cards. We take out the smallest card from the priority queue and try to form a group of W cards starting from that card.

4. If a group of W cards is formed, we decrement the frequency of all those cards in the hash map. We also remove them from the priority queue if their frequency becomes zero.

5. If we are unable to form a group of W cards starting from the smallest card, we return false.

6. We repeat steps 3-5 until all cards have been processed.

7. If we are able to form groups of W cards for all cards, we return true.

Here is the implementation of the above steps in Python:

class Solution: def isNStraightHand(self, hand: List[int], W: int) -> bool: # Count frequency of each card freq = collections.Counter(hand)

    # Initialize a priority queue with the keys of the frequency map
    pq = queue.PriorityQueue()
    for key in freq:
        pq.put(key)
    
    # Process cards in ascending order of value
    while not pq.empty():
        start = pq.get()
        for i in range(W-1):
            next_card = start + i + 1
            if next_card not in freq:
                return False
            if freq[next_card] == 0:
                return False
            freq[next_card] -= 1
            if freq[next_card] == 0:
                del freq[next_card]
    
    # All cards have been processed
    return True

The time complexity of this solution is O(n log n) because we are using a priority queue for processing the cards. The space complexity is O(n) because we are using a hash map to store the frequency of each card.

1