Greedy crash course ↗ · 84

846. Hand of Straights

Given a hand of cards, decide whether they can be arranged into groups of groupSize consecutive integers. The key insight: always start a new group from the smallest unused card — any other choice leads to a dead end.

● MediumGreedyHash Map / CountingSortingTypeScript

PROBLEM What we're solving

You hold a hand of integers. Decide whether you can rearrange all of them into groups where each group has exactly groupSize consecutive cards (e.g. 3, 4, 5 or 7, 8, 9). Every card must be used exactly once.

Example: hand = [1,2,3,6,2,3,4,7,8,2,3,5], groupSize = 3. The twelve cards split into four groups: [1,2,3], [2,3,4], [2,3,5], [6,7,8]. Return true. If groupSize = 4 for the same hand (12 cards), we would need three groups of 4; with groupSize = 5we'd need two groups of 5. Whenever hand.length % groupSize !== 0, immediately return false.

KEY IDEA Greedy: always lead with the smallest card

Insight → The smallest remaining card must start a new run — it can never be the second or later card in a group (there is no card smaller to precede it). So greedily open a run of groupSize starting there, consuming one copy each of the next groupSize − 1 consecutive cards. If any of those cards is unavailable, the whole arrangement is impossible.

RECIPE Count → sort keys → peel from smallest

  • 0 · Quick reject. If hand.length % groupSize !== 0, no valid split exists. Return false immediately.
  • 1 · Count cards. Build a Map<number, number> of card → frequency. Every distinct value becomes a key.
  • 2 · Sort the keys. Extract all keys and sort them ascending so we always process the smallest remaining card first.
  • 3 · Peel runs. For each key start (skip if its count is already 0): let freq = count[start]. We must open freq separate runs beginning here, each consuming one card from start through start + groupSize − 1. If any card in that range has fewer than freq copies, return false; otherwise subtract freq from each.
  • 4 · All consumed. If we exhaust the sorted keys without failing, return true.
Classic confusion → Many solutions subtract only one from each consecutive card per outer-loop iteration, iterating over the hand repeatedly. The efficient version realizes that if count[start] = freq, all freq groups starting at start must be processed at once — subtract freq from each card in the range in a single inner pass, not one at a time.

COST Complexity & alternatives

Sort hand, scan linearly
O(n log n)
Sort + O(n·groupSize) in the worst case if done naively.
Count map + sort distinct keys
O(n log n)
Sort k distinct keys; inner loop totals O(n). Space: O(k).

Both approaches are O(n log n) due to sorting, but the count-map version avoids physically rearranging all n cards — it sorts only the distinct values (k ≤ n). The inner loop over groupSize slots runs once per unique starting value and in total touches each card at most once, keeping the work at O(n) after sorting.

Pattern transfer →The same "smallest-first greedy on a frequency map" idea appears in Divide Array in Sets of K Consecutive Numbers (LC 1296, an exact restatement), Task Scheduler (always schedule the most-frequent task first), and Reorganize String (greedy on counts to prevent adjacent duplicates). Any time you must pair or chain items with no adjacent repetition, reach for a sorted-key frequency map.

RUN IT Count cards; greedily peel runs from the smallest

step 0 / 8
STARTHand: [1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8]. Group size: 3. Build a frequency count; then greedily peel runs from the smallest card.
1function isNStraightHand(hand: number[], groupSize: number): boolean {
2  if (hand.length % groupSize !== 0) return false;
3 
4▶  const count = new Map<number, number>();
5▶  for (const card of hand) {
6▶    count.set(card, (count.get(card) ?? 0) + 1);
7▶  }
8 
9  const keys = [...count.keys()].sort((a, b) => a - b);
10 
11  for (const start of keys) {
12    const freq = count.get(start) ?? 0;
13    if (freq === 0) continue;          // already fully consumed
14 
15    // We need to open freq groups starting at 'start'
16    for (let i = 0; i < groupSize; i++) {
17      const card = start + i;
18      const available = count.get(card) ?? 0;
19      if (available < freq) return false;   // can't complete all freq groups
20      count.set(card, available - freq);
21    }
22  }
23 
24  return true;
25}
hand:122233345678
Letter countsinitial counts
1
1
3
2
3
3
1
4
1
5
1
6
1
7
1
8
current card being consumedcards in active runmissing card — run failsfully consumed
slowfast

TYPESCRIPT The solution, annotated

isNStraightHand.ts
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;

  const count = new Map<number, number>();
  for (const card of hand) {
    count.set(card, (count.get(card) ?? 0) + 1);
  }

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

  for (const start of keys) {
    const freq = count.get(start) ?? 0;
    if (freq === 0) continue;          // already fully consumed

    // We need to open freq groups starting at 'start'
    for (let i = 0; i < groupSize; i++) {
      const card = start + i;
      const available = count.get(card) ?? 0;
      if (available < freq) return false;   // can't complete all freq groups
      count.set(card, available - freq);
    }
  }

  return true;
}

Reading it block by block

Line 2 — divisibility check. If the total card count isn't divisible by groupSize, no valid partition exists. This O(1) check avoids any further work.
Lines 4–7 — build the frequency map. Count how many copies of each card value exist. Using a Map keeps the keys as numbers (not strings), which matters when sorting later.
Line 9 — sort distinct keys. We extract every key that appears and sort numerically. Sorting by the integer values (not lexicographically) is why we pass a comparator (a, b) => a - b.
Lines 11–20 — the greedy peel. For each starting value, skip if already exhausted (freq === 0). Otherwise we know freq separate groups must start here, each needing one copy of start through start + groupSize - 1. We check availability and subtract in one inner pass — this is the key efficiency trick.
Line 23 — return true. If the loop completes without returning false, every card has been assigned to a valid consecutive group.
Complexity → O(n log n) for sorting k distinct keys (k ≤ n); the frequency-peel loop is O(n) total since each card is subtracted at most once. Space: O(k) for the map.

INTERVIEWFollow-ups they'll ask

  • "What if groupSize = 1?" Every single card forms a group of one — always true as long as hand.length % 1 === 0, which is trivially true.
  • "Can you do it without sorting?" You could use a sorted set (like a balanced BST) to always get the minimum in O(log n), making the algorithm O(n log n) with a constant-factor improvement. In JS/TS there is no built-in sorted set, so sorting the keys is the idiomatic choice.
  • "What if cards can repeat arbitrarily many times?" The algorithm already handles this — the outer loop processes all frequencies at each unique starting value in one batch via the freq subtraction.
  • "Return the actual groups, not just true/false?" Reconstruct during the peel: push [start, start+1, ..., start+groupSize-1] into a result array freq times (or store the groups as a 2-D array built alongside the subtraction loop).
  • "Heap-based approach?" A min-heap replacing the sorted-key array is the classic alternative — same O(n log k) complexity but uses O(k) heap space and the same greedy logic. Good to mention as a generalisation.

OPTIMAL Greedy

isNStraightHand.ts
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;

  const count = new Map<number, number>();
  for (const card of hand) {
    count.set(card, (count.get(card) ?? 0) + 1);
  }

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

  for (const start of keys) {
    const freq = count.get(start) ?? 0;
    if (freq === 0) continue;          // already fully consumed

    // We need to open freq groups starting at 'start'
    for (let i = 0; i < groupSize; i++) {
      const card = start + i;
      const available = count.get(card) ?? 0;
      if (available < freq) return false;   // can't complete all freq groups
      count.set(card, available - freq);
    }
  }

  return true;
}
Complexity → O(n log n) for sorting k distinct keys (k ≤ n); the frequency-peel loop is O(n) total since each card is subtracted at most once. Space: O(k) for the map.

ALT 1 Brute force — repeatedly pull a run starting at the smallest card

O(n² log n) time · O(n) space

Keep the hand sorted. Repeatedly take the current smallest card as the start of a run, then linearly search-and-remove the next groupSize - 1consecutive values. If any is missing, it's impossible.

approach-2.ts
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;

  const cards = [...hand].sort((a, b) => a - b);

  while (cards.length > 0) {
    const start = cards.shift() as number;   // smallest remaining
    for (let i = 1; i < groupSize; i++) {
      const next = start + i;
      const idx = cards.indexOf(next);       // linear search
      if (idx === -1) return false;
      cards.splice(idx, 1);                  // remove one copy
    }
  }

  return true;
}
Note → Each run does up to groupSize linear searches and splices over an O(n) array, giving O(n²) work plus the initial sort. Counting card frequencies in a map and consuming runs by arithmetic lookup removes the inner scan.

MNEMONIC The one-liner

"Smallest card has nowhere to hide — it must lead. Peel it and its next groupSize-1 friends, or fail."

TRIGGERS When you see ___ → reach for ___

"consecutive groups of size k"sorted frequency map + greedy peel from min
arrange cards / tasks into fixed-length chainscount + smallest-first greedy
hand.length % groupSize !== 0instant false — divisibility guard first
"Divide array in sets of k consecutive"same pattern as Hand of Straights

SKELETON The reusable shape

skeleton.ts
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize !== 0) return false;
  const count = new Map<number, number>();
  for (const card of hand) count.set(card, (count.get(card) ?? 0) + 1);

  const keys = [...count.keys()].sort((a, b) => a - b);
  for (const start of keys) {
    const freq = count.get(start) ?? 0;
    if (freq === 0) continue;
    for (let i = 0; i < groupSize; i++) {
      const card = start + i;
      const available = count.get(card) ?? 0;
      if (available < freq) return false;
      count.set(card, available - freq);
    }
  }
  return true;
}

FLASHCARDS Tap to flip

Why must the smallest card always start a new group?
No smaller card exists to precede it, so it has exactly one role: the beginning of a consecutive run.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the optimal solution for isNStraightHand?
QUESTION 02
What is the very first check, before any map building?
QUESTION 03
For hand = [1,2,3,6,2,3,4,7,8,2,3,5], groupSize = 3, how many distinct groups are formed?
QUESTION 04
Why do we subtract freq (not 1) from each card in the consecutive window?
QUESTION 05
hand = [1,2,3,4], groupSize = 3. What does the algorithm return?
QUESTION 06
What data structure drives the "always process the smallest card first" guarantee?
QUESTION 07
During the peel, we check available < freq for a card mid-run. What does this failing mean?
QUESTION 08
#846 · Hand of StraightsCount card frequencies in a sorted map. Repeatedly start a consecutive run at the smallest remaining card and consume the next groupSize−1 successive values; fail immediately if any required card is missing.Which algorithmic approach does this primarily use?
QUESTION 09
#846 · Hand of StraightsCount card frequencies in a sorted map. Repeatedly start a consecutive run at the smallest remaining card and consume the next groupSize−1 successive values; fail immediately if any required card is missing.Which implementation correctly solves it?