846. Hand of Straights

[mah-shamim]

Topics: Array, Hash Table, Greedy, Sorting

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.

Example 3:

• Input: hand = [2,1], groupSize = 2
• Output: true
• Explanation: Alice's hand can not be rearranged into groups of 2.

Constraints:

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

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

[basharul-siddike]

The goal is to determine whether the array hand can be rearranged into groups of consecutive cards where each group has a size of groupSize.

Approach:

1. Key Idea:

   • We can use a greedy approach: first sort the cards, then attempt to form consecutive groups starting from the smallest card.
   • For each group, reduce the count of each card as they are used to form the group. If any group can't be formed because a card is missing or insufficient in quantity, return false.

2. Frequency Count:

   • Use a hash table (associative array in PHP) to count the frequency of each card. This helps track how many of each card is available.

3. Greedy Strategy:

   • Sort the array to ensure that we always start forming groups from the smallest available card.
   • For each card, try to form a group of groupSize consecutive cards.
   • Decrease the count of each card in the group. If we can't find enough cards to form a valid group, return false.

4. Edge Case:

   • If the total number of cards is not divisible by groupSize, it's impossible to divide them into valid groups, so we can return false early.

Let's implement this solution in PHP: 846. Hand of Straights

<?php
/**
 * @param Integer[] $hand
 * @param Integer $groupSize
 * @return Boolean
 */
function isNStraightHand($hand, $groupSize) {
    $n = count($hand);

    // Early return if the number of cards is not divisible by groupSize
    if ($n % $groupSize != 0) {
        return false;
    }

    // Step 1: Count frequency of each card using a hash table
    $count = [];
    foreach ($hand as $card) {
        if (isset($count[$card])) {
            $count[$card]++;
        } else {
            $count[$card] = 1;
        }
    }

    // Step 2: Sort the hand to ensure we start from the smallest card
    sort($hand);

    // Step 3: Try to form groups starting from the smallest card
    foreach ($hand as $card) {
        // If this card has already been used up, skip it
        if ($count[$card] == 0) {
            continue;
        }

        // Try to form a group of consecutive cards
        for ($i = 0; $i < $groupSize; $i++) {
            $currentCard = $card + $i;
            // If the card is missing or insufficient in number, return false
            if (!isset($count[$currentCard]) || $count[$currentCard] == 0) {
                return false;
            }
            // Decrease the count of the current card
            $count[$currentCard]--;
        }
    }

    // If we successfully formed all the groups, return true
    return true;
}

// Example 1
$hand1 = [1,2,3,6,2,3,4,7,8];
$groupSize1 = 3;
echo isNStraightHand($hand1, $groupSize1) ? 'true' : 'false'; // Output: true

// Example 2
$hand2 = [1,2,3,4,5];
$groupSize2 = 4;
echo isNStraightHand($hand2, $groupSize2) ? 'true' : 'false'; // Output: false

// Example 3
$hand3 = [2,1];
$groupSize3 = 2;
echo isNStraightHand($hand3, $groupSize3) ? 'true' : 'false'; // Output: true
?>

Explanation:

1. Frequency Count ($count):

   • We use an associative array to store how many times each card appears in the hand.

2. Sort the Hand:

   • We sort the hand so that we always try to form groups starting from the smallest card, which simplifies the process of finding consecutive cards.

3. Greedy Group Formation:

   • For each card in the sorted hand:
     • If the card has been fully used up in previous groups (i.e., its count is 0), skip it.
     • Attempt to form a group of groupSize consecutive cards starting from this card.
     • If we can't find enough consecutive cards to form a group, return false.
   • If we successfully form all the required groups, return true.

Time Complexity:

• Sorting the array takes O(n log n), where n is the length of the hand.
• Forming the groups takes O(n x groupSize), but since we visit each card at most once, this is O(n).
• Overall time complexity: O(n log n).

Output:

For hand = [1,2,3,6,2,3,4,7,8] and groupSize = 3, the output is:

true

For hand = [1,2,3,4,5] and groupSize = 4, the output is:

false

For hand = [2,1] and groupSize = 2, the output is:

true

This solution efficiently checks if the hand can be rearranged into consecutive groups.

[mah-shamim]

Thanks to solve the "Hand of Straights" problem

[basharul-siddike]

Thanks