algoadvance

Alice has a hand of cards, each card has a card number printed on it. Alice wants to rearrange the cards into groups so that each group is of size W, and consists of W consecutive cards.

Given an integer array hand of size n where hand[i] is the value written on the i-th card and an integer W, return true if and only if she can rearrange the cards into groups of size W, or false otherwise.

Clarifying Questions

  1. What should be done if n is not a multiple of W?
    • The length of the hand should be a multiple of W to form W groups. If not, return false.
  2. What kinds of values can the cards have?
    • The values of the cards are integers, which can be negative, zero, or positive.
  3. Do we need to handle any specific edge cases?
    • Yes, if hand is empty, the result is trivially true. If W is 1, the result is trivially true because each individual card can be its own group.

Strategy

  1. Check for Trivially Impossible Cases: If the size of the hand n is not a multiple of W, return false immediately.
  2. Sort the Cards: Sorting the hand array will allow us to easily check for consecutive sequences.
  3. Use a Counter: Use a counter to maintain the frequency of each card.
  4. Form Consecutive Groups:
    • Iterate through the sorted hand array.
    • For each card, if it still needs to be placed in a group, try to form a consecutive group starting from that card.
    • Reduce the count of cards as they are placed in groups.

Time Complexity

Overall, the time complexity is (O(n \log n + n \cdot W)).

Code

from collections import Counter

def isNStraightHand(hand, W):
    if len(hand) % W != 0:
        return False
    
    count = Counter(hand)
    
    for num in sorted(count):
        if count[num] > 0:  # Only if the card needs to be part of a group
            card_count = count[num]
            for i in range(W):
                if count[num + i] < card_count:
                    return False
                count[num + i] -= card_count
    
    return True

# Example usage
print(isNStraightHand([1,2,3,6,2,3,4,7,8], 3))  # Expected output: True
print(isNStraightHand([1,2,3,4,5], 4))  # Expected output: False

This code uses a Counter to track the frequency of each card. It then sorts the cards and tries to form groups starting with the smallest card available. If at any point it can’t form a required group, it returns false. If it successfully forms all required groups, it returns true.

Try our interview co-pilot at AlgoAdvance.com