Hand of Straights

The problem

hand is a list of cards, each a whole number, in no particular order. Return true if all the cards can be divided into groups of exactly groupSize cards whose values are consecutive: each value is 1 more than the one before, such as 4, 5, 6. Return false otherwise. Every card belongs to exactly one group, and two cards with the same value are two separate cards.

What to write

function solve(hand: number[], groupSize: number): boolean

Input
hand = [1,2,3,6,2,3,4,7,8]
groupSize = 3

Output
true

Input
hand = [1,2,3,4,5]
groupSize = 4

Output
false

Constraints

groupSize is positive.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every group holds exactly groupSize cards, so the number of cards in the hand already rules some hands out. The values in a group are all different, so two cards with the same value can never share a group.

2. Hint 2: Ask a smaller question

   Take the hand 2, 1, 3, 2 with groups of 2. Find a card whose group you can name without trying anything. What makes that card special? Once that group is set aside, can you do the same again?

3. Hint 3: Name the pattern

   The smallest card left has no smaller card below it, so it must be the lowest card of its group, and the rest of that group is forced. A step you can commit to and never take back is a greedy choice. Count the cards of each value first, so each step is quick. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   When you reach a value, every smaller value is already used up. So each card left of this value must start a group. That group is groupSize values in a row, beginning with this one, and it needs one card of each.

5. Hint 5: Sketch the pseudocode

   Return false if the number of cards is not a multiple of groupSize. Count the cards of each value. For each value v, smallest first: c = cards left of v. If c is above 0, for each value from v to v + groupSize - 1: return false if fewer than c are left, else remove c. Return true.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

The smallest remaining card must begin a group. Consume enough consecutive cards to satisfy every copy of that smallest value.

The slow way

Pick any card, try it as the lowest card of a group, take that group out and go on with the rest. When you get stuck, put the group back and try another card. This is correct, but it gives up on a hand only after every order has failed. With six separate pairs and two cards that fit nowhere, that is 720 orders of taking the pairs out.

The insight

The smallest card left cannot sit above another card of its group, because that would need a smaller card and there is none. So it is the lowest card of its group, and the other cards of that group are fixed. A step that is forced like this never has to be undone: a greedy choice.

Step by step

1. A hand whose size is not a multiple of groupSize cannot be divided. Full groups of groupSize cards always add up to a multiple of groupSize. The later steps would also answer false for such a hand. This test answers before any counting.
2. Count how many cards there are of each value. Where a card sits in the hand does not matter. What matters is how many cards of each value are still unused, and a count per value answers that in one lookup.
3. Go through the values from smallest to largest. The smallest value still unused has no smaller card below it, so its place in a group is known. Going upward makes the same true for each value in turn. This is where the values get sorted.
4. Every card left of this value has to start a group. All smaller values are used up by now, so each card left can only be the lowest card of a new group, which runs upward from this value. With no card left, the value is skipped.
5. Too few cards of a value those groups need: the answer is false. Each of those groups needs one card of that value. If there are not enough, one group can never be completed, and its lowest card had nowhere else to go.
6. Otherwise take one card of that value for each group. Those cards now belong to the groups that started here. Taking them out of the count stops a later value from using them a second time.
7. Every card has been placed in a group. Each value's count went down to zero when its turn came, and no group was left unfinished. So all the cards sit in complete groups of consecutive values.

The same numbered steps are the comments in each solution.

function solve(hand, groupSize) {
  // 1. A hand whose size is not a multiple of groupSize cannot be divided
  if (hand.length % groupSize) return false;
  // 2. Count how many cards there are of each value
  const counts = new Map();
  for (const n of hand) counts.set(n, (counts.get(n) || 0) + 1);
  // 3. Go through the values from smallest to largest
  for (const start of [...counts.keys()].sort((a, b) => a - b)) {
    // 4. Every card left of this value has to start a group
    const count = counts.get(start);
    if (!count) continue;
    for (let n = start; n < start + groupSize; n++) {
      // 5. Too few cards of a value those groups need: the answer is false
      if ((counts.get(n) || 0) < count) return false;
      // 6. Otherwise take one card of that value for each group
      counts.set(n, counts.get(n) - count);
    }
  }
  // 7. Every card has been placed in a group
  return true;
}

function solve(hand: number[], groupSize: number): boolean {
  // 1. A hand whose size is not a multiple of groupSize cannot be divided
  if (hand.length % groupSize) return false;
  // 2. Count how many cards there are of each value
  const counts = new Map<number, number>();
  for (const n of hand) counts.set(n, (counts.get(n) || 0) + 1);
  // 3. Go through the values from smallest to largest
  for (const start of [...counts.keys()].sort((a, b) => a - b)) {
    // 4. Every card left of this value has to start a group
    const count = counts.get(start)!;
    if (!count) continue;
    for (let n = start; n < start + groupSize; n++) {
      // 5. Too few cards of a value those groups need: the answer is false
      if ((counts.get(n) || 0) < count) return false;
      // 6. Otherwise take one card of that value for each group
      counts.set(n, counts.get(n)! - count);
    }
  }
  // 7. Every card has been placed in a group
  return true;
}

def solve(hand, groupSize):
    # 1. A hand whose size is not a multiple of groupSize cannot be divided
    if len(hand) % groupSize:
        return False
    # 2. Count how many cards there are of each value
    counts = {}
    for num in hand:
        counts[num] = counts.get(num, 0) + 1
    # 3. Go through the values from smallest to largest
    for start in sorted(counts):
        # 4. Every card left of this value has to start a group
        count = counts[start]
        if not count:
            continue
        for num in range(start, start + groupSize):
            # 5. Too few cards of a value those groups need: the answer is false
            if counts.get(num, 0) < count:
                return False
            # 6. Otherwise take one card of that value for each group
            counts[num] -= count
    # 7. Every card has been placed in a group
    return True

Example 1, traced

Input
hand = [1,2,3,6,2,3,4,7,8]
groupSize = 3

Output
true

Why it works

When the method reaches a value, every smaller value is used up. So however the remaining cards are divided, each card of this value is the lowest card of its group, and the other values of that group are fixed. The method builds exactly these forced groups. If one cannot be completed, the hand cannot be divided. If all are, every card is placed.

Time and space

Time O(n log n), extra space O(n). Counting reads all n cards. Sorting the values costs the most, about n log n steps: O(n log n) time. Taking cards for the groups adds at most n rounds: each round that does not fail uses up a card. The count holds up to n values: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not sort the cards and cut them into chunks of groupSize. In example 1 the sorted hand starts 1, 2, 2, and that chunk does not count up by one. The answer comes out false instead of true.
• Go through the values in sorted order. In the order they appear in the hand, the hand 2, 1 with groups of 2 gives false: 2 is asked to start a group first, and there is no 3.
• Each card left of a value starts its own group. Start only one group per value and the hand 1, 1, 2, 2, 3, 3 with groups of 3 gives false, because the value 2 looks for a 4.

Pattern

Greedy choice. Builds on Valid Anagram and Longest Consecutive Sequence.

Keep going