Hand of Straights

Hand of Straights

What is this problem about?

The Hand of Straights interview question asks you to determine if a given array of integers (hand of cards) can be rearranged into groups of a specific size groupSize, where each group consists of consecutive integers. For example, if groupSize is 3, a valid group could be [1, 2, 3]. Every card in the hand must be part of exactly one group.

Why is this asked in interviews?

This problem is popular at companies like Apple and Amazon because it tests a candidate's ability to apply a greedy interview pattern to a collection of data. It evaluation whether you can efficiently manage counts of elements and identify the "bottleneck" (the smallest available card). It requires a combination of Hash Table for frequency counting and Sorting or an Ordered Set to process elements in the correct order.

Algorithmic pattern used

The problem is solved using a Greedy approach with Frequency Counting.

1. First, check if the total number of cards is divisible by groupSize. If not, return false.
2. Count the frequency of each card using a Hash Map.
3. Sort the unique card values (or use a TreeMap/Min-Heap).
4. Pick the smallest card $X$ that still has a positive count.
5. Try to form a group starting from $X$: $[X, X+1, \dots, X + groupSize - 1]$.
6. For each card in this group, decrement its count in the map. If any card is missing or has a count of 0, return false.
7. Repeat until all cards are processed.

Example explanation

Hand: [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3.

1. Frequencies: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}.
2. Smallest is 1. Need [1, 2, 3].
   • New Frequencies: {2:1, 3:1, 4:1, 6:1, 7:1, 8:1}.
3. Smallest remaining is 2. Need [2, 3, 4].
   • New Frequencies: {6:1, 7:1, 8:1}.
4. Smallest remaining is 6. Need [6, 7, 8].
   • All counts hit zero. Result: True.

Common mistakes candidates make

• Not Processing in Order: Trying to form groups without starting from the smallest available card, which makes it hard to track remaining possibilities.
• Inefficient Deletion: Not using a proper frequency map, leading to $O(n^2)$ search times.
• Ignoring Duplicates: Failing to realize that multiple groups can start with the same value (e.g., two [1, 2, 3] groups).

Interview preparation tip

Whenever you have a problem involving "consecutive groups," always process from the minimum value. This ensures that the smallest element must be the start of a group, which simplifies the decision logic and avoids the need for backtracking.