We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Hand of Straights

Number: 876

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Microsoft, Amazon

Problem Description

Given an array of integers representing card values and a group size, determine if it is possible to rearrange the cards into groups where each group consists of consecutive cards of size equal to groupSize.

Key Insights

  • The total number of cards must be divisible by groupSize.
  • Use a frequency count (hash table or map) to record the occurrence of each card.
  • Always start forming groups from the smallest available card to maintain the consecutive order.
  • For each card, if its count is non-zero, check that the subsequent groupSize-1 cards exist with at least as many counts.
  • Decrease the counts accordingly for each valid consecutive group.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the unique keys from the hand. Space Complexity: O(n) for storing the frequency count of the cards.

Solution

The solution uses a greedy approach along with a frequency hash map. The main steps are:

  1. Verify that the total number of cards is divisible by groupSize.
  2. Count the frequency of each card.
  3. Sort the keys of the frequency map.
  4. Iterate over the sorted keys and for each card with a positive count, try to form a group of groupSize consecutive cards.
  5. For each card in the group, decrease the frequency by the number of groups formed. If at any point the required card is missing or its count is insufficient, return false.
  6. If all groups can be formed successfully, return true.

Code Solutions

# Python solution using collections.Counter for frequency mapping
from collections import Counter

def isNStraightHand(hand, groupSize):
    # Check whether total cards can be divided into groups of groupSize
    if len(hand) % groupSize != 0:
        return False

    # Create frequency map of cards
    card_count = Counter(hand)
    
    # Process sorted keys to ensure we always start with the smallest available card
    for card in sorted(card_count.keys()):
        # If current count is greater than 0, try to form a consecutive group starting from card
        count = card_count[card]
        if count > 0:
            for i in range(groupSize):
                # Check if consecutive card exists in sufficient quantity
                if card_count[card + i] < count:
                    return False
                # Deduct the frequency for the current group
                card_count[card + i] -= count
    return True

# Example usage:
# print(isNStraightHand([1,2,3,6,2,3,4,7,8], 3))  # Expected output: True
← Back to All Questions