Hand of Straights

Examples

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

The hand splits into [1,2,3], [2,3,4], and [6,7,8], each a run of 3 consecutive numbers.

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

5 cards can't be split evenly into groups of 4.

Input: hand = [8, 10, 12], groupSize = 3
Output: false

No 3 of these numbers are consecutive, so no valid group can be formed.

Constraints

• 1 <= hand.length <= 10^4

• 0 <= hand[i] <= 10^9

• 1 <= groupSize <= hand.length

Approach

The trick is to always look at the smallest card value still remaining in the hand. That card can only ever be the start of a consecutive run in whatever group it belongs to - since no smaller value exists in the hand to place before it. This removes any ambiguity about which group a card should join, so you can build groups greedily.

Count how many copies of each value you hold. Repeatedly take the smallest value with a remaining count greater than zero, and consume one card each of that value and the next groupSize - 1 consecutive values. If at any point a needed consecutive value isn't available, the hand can't be split.

Solutions

Brute Force - Sort and Greedily Remove

Sort the cards. Repeatedly take the smallest remaining card and try to remove groupSize consecutive values from the sorted list, re-searching the array each time.

function isNStraightHand(hand, groupSize) {
  if (hand.length % groupSize !== 0) return false;
  const remaining = [...hand].sort((a, b) => a - b);

  while (remaining.length > 0) {
    const start = remaining[0];
    const used = [];
    for (let need = start; need < start + groupSize; need++) {
      const idx = remaining.indexOf(need);
      if (idx === -1) return false;
      used.push(idx);
    }
    used.sort((a, b) => b - a);
    for (const idx of used) remaining.splice(idx, 1);
  }
  return true;
}

Time: O(n^2 / groupSize) due to repeated linear scans and splices · Space: O(n)

Optimal - Count Map + Smallest-First Greedy

Count each value's frequency. Always start a new group at the smallest value with a positive count, and consume groupSize consecutive values from the count map.

function isNStraightHand(hand, groupSize) {
  if (hand.length % groupSize !== 0) return false;

  const count = new Map();
  for (const card of hand) count.set(card, (count.get(card) || 0) + 1);

  const sortedValues = [...count.keys()].sort((a, b) => a - b);

  for (const value of sortedValues) {
    const need = count.get(value);
    if (need > 0) {
      for (let v = value; v < value + groupSize; v++) {
        const have = count.get(v) || 0;
        if (have < need) return false;
        count.set(v, have - need);
      }
    }
  }
  return true;
}

Time: O(n log n), dominated by sorting the distinct values · Space: O(n)