Frontend Beauty
ESC

Type to search the knowledge base.

Hand of Straights

Split hand into groups of W consecutive cards — sorted map/counting greedy, fail when a needed card is missing.

intermediate3 min read
  • dsa
  • greedy
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

hand of card values; groupSize (W). Return true if cards can be rearranged into groups of W consecutive values each.

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 → true
// [1,2,3], [2,3,4], [6,7,8]
hand = [1,2,3,4,5], groupSize = 4 → false

Same as “Alice’s Hand” / divide array in sets of k consecutive.

Brute

Generate all partitions — factorial explosion. Skip.

Greedy with counts

  1. If hand.length % W !== 0 → false.
  2. Count frequencies (Map).
  3. Repeatedly take the smallest remaining value as start of a group; consume start..start+W-1 one each.
  4. If any missing → false.
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;

  const freq = new Map<number, number>();
  for (const x of hand) freq.set(x, (freq.get(x) ?? 0) + 1);

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

  for (const start of keys) {
    const need = freq.get(start) ?? 0;
    if (need === 0) continue;
    for (let x = start; x < start + groupSize; x++) {
      const c = freq.get(x) ?? 0;
      if (c < need) return false;
      freq.set(x, c - need);
    }
  }
  return true;
}

When we process start, need is how many groups must start at start (all remaining copies of start must start a group). Consume that many from each consecutive value.
Time O(n log n) sort unique keys + O(n · W)
Space O(n)

Optimized note

With a balanced tree map (TreeMap) you always poll min key — same idea. JS: sort keys once is fine if you skip zeros.

Edge cases

  • groupSize = 1 → always true
  • Duplicates needed for parallel groups
  • Gaps in numbers
  • Negative values (if allowed)

Common mistakes

  • Only checking multiset can form one sequence
  • Sorting hand and sliding fixed windows without counts
  • Forgetting length % W

Interview delivery

  1. Length divisible by W.
  2. Count + greedy from smallest.
  3. Consume consecutive run.
  4. Trace failure on gap.
  5. Complexity.

Mental model

Greedy from the smallest remaining card: it must open a straight, so commit as many straights as there are copies of that card, consuming the next W−1 values. If any count goes negative / missing, fail.

This is the same spirit as reconstructing sequences with a multiset.

Alternative structures

  • TreeMap / sorted map: always poll minimum key.
  • Sort the hand array and two-pointer — messier with duplicates.
  • Count map + sorted keys (what we coded) is interview-friendly in JS.

Out-loud answer

“If length not divisible by groupSize, false. Frequency map, sort unique keys, from each start consume groupSize consecutive values need times. Missing count → false. O(n log n).”

Further reading