Hand of Straights

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Greedy Algorithms, Hash Maps, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does it mean for a group to be a run of consecutive values?

  • A: The group_size cards in a group must form values like [2, 3, 4], each exactly one greater than the previous. Duplicates in the hand are fine, but a single group cannot contain a repeated value.

• Q: Do all cards in the hand have to be used?

  • A: Yes. The entire hand must be rearranged into groups; leftover cards mean the answer is False.

• Q: Is there a quick way to rule out some hands immediately?

  • A: Yes. If len(hand) is not divisible by group_size, the cards cannot possibly form equal-sized groups, so return False right away.

HAPPY CASE
Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], group_size = 3
Output: True
Explanation: The hand can be rearranged into the groups [1, 2, 3], [2, 3, 4], and [6, 7, 8], each a run of 3 consecutive values.

EDGE CASE
Input: hand = [1, 2, 3, 4, 5], group_size = 4
Output: False
Explanation: There are 5 cards, which cannot be divided into groups of 4.

Input: hand = [1, 2, 3, 5], group_size = 2
Output: False
Explanation: The length divides evenly, but after pairing [1, 2] the remaining cards [3, 5] are not consecutive, and no other pairing works.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Grouping/Partitioning Problems, we can consider the following approaches:

• Greedy: The smallest remaining card has no smaller neighbor, so it must start a group. Committing it (and the consecutive cards after it) is always safe.
• Hash Map (Counting): A frequency map tracks how many copies of each card value remain as groups are formed.
• Sorting: Processing card values in ascending order guarantees the greedy choice is applied to the smallest remaining card first.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Count the frequency of every card value, then walk the values in sorted order. Whatever the smallest remaining card is, every copy of it must begin its own group, so the next group_size - 1 consecutive values must each have at least that many copies available. Deduct those copies and continue; if any required value falls short, the hand cannot be arranged.

1) If len(hand) is not divisible by group_size, return False.
2) Build a frequency map `counts` of the card values.
3) For each card value in sorted order:
   a) Let `count` be the remaining copies of this value.
   b) If `count` > 0, this value must start `count` groups:
      i)  For each value v from card to card + group_size - 1:
          - If counts[v] < count, return False (not enough cards to complete the runs).
          - Subtract count from counts[v].
4) If every value is consumed, return True.

⚠️ Common Mistakes

• Forgetting the early len(hand) % group_size != 0 check, which the main loop does not otherwise catch.
• Deducting only one copy of each consecutive value instead of count copies — every copy of the smallest card starts its own group.
• Iterating over the hand in its original order instead of sorted order, which breaks the greedy guarantee.

4: I-mplement

Implement the code to solve the algorithm.

from collections import Counter

def is_n_straight_hand(hand, group_size):
    # The hand must divide evenly into groups
    if len(hand) % group_size != 0:
        return False

    counts = Counter(hand)

    # Process card values from smallest to largest
    for card in sorted(counts):
        count = counts[card]
        if count > 0:
            # The smallest remaining card must start `count` groups,
            # so each of the next group_size consecutive values must
            # appear at least `count` times
            for next_card in range(card, card + group_size):
                if counts[next_card] < count:
                    return False
                counts[next_card] -= count

    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], group_size = 3

  • counts = {1: 1, 2: 2, 3: 2, 4: 1, 6: 1, 7: 1, 8: 1}
  • card 1 (count 1): deduct one copy each of 1, 2, 3 → forms [1, 2, 3]; counts = {2: 1, 3: 1, 4: 1, 6: 1, 7: 1, 8: 1}
  • card 2 (count 1): deduct one copy each of 2, 3, 4 → forms [2, 3, 4]; counts = {6: 1, 7: 1, 8: 1}
  • card 6 (count 1): deduct one copy each of 6, 7, 8 → forms [6, 7, 8]; all cards consumed.
  • Output: True

• Input: hand = [1, 2, 3, 4, 5], group_size = 4

  • len(hand) = 5 is not divisible by 4, so the function returns immediately.
  • Output: False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of cards in the hand and K is group_size.

• Time Complexity: O(N log N) to sort the distinct card values; forming groups deducts each of the N cards exactly once, so the greedy pass adds only O(N) work.
• Space Complexity: O(N) for the frequency map (and the sorted list of distinct values).