Hand of Straights

GREEDY · MEDIUM

The problem

Alice has a hand of cards, given as an array of integers hand. She wants to rearrange every card into groups of exactly groupSize, where each group is made of groupSize consecutive integers (like {5, 6, 7} for groupSize = 3). Every card must end up in exactly one group. Return true if this is possible, or false otherwise.

Solution 1: Brute force — same greedy idea, repeated linear scans

The greedy insight is unavoidable even in a naive version: the smallest card left in your hand can never belong to any group except one that starts exactly at it, so you always pull the current minimum and try to build a run from there. The brute-force version does exactly that, but on a plain working array — Math.min-style linear scan to find the smallest card, then indexOf + splice to find and remove each of the next groupSize - 1 consecutive values, one at a time. Every one of those operations re-scans the array from scratch.

hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3 — hand=[1,2,3,6,2,3,4,7,8], groupSize=3 — LeetCode's own canonical example (expected: true)

Press play to run the brute-force algorithm.

Step 0 / 14

The code

function isNStraightHandBrute(hand, groupSize) {
  if (hand.length % groupSize !== 0) return false;
  const working = hand.slice();

  while (working.length > 0) {
    // Linear scan for the smallest remaining card.
    let minIdx = 0;
    for (let i = 1; i < working.length; i++) {
      if (working[i] < working[minIdx]) minIdx = i;
    }
    const start = working[minIdx];
    working.splice(minIdx, 1);

    // One indexOf + splice per remaining group member.
    for (let k = 1; k < groupSize; k++) {
      const need = start + k;
      const idx = working.indexOf(need);
      if (idx === -1) return false;
      working.splice(idx, 1);
    }
  }
  return true;
}

Line by line:

hand.length % groupSize !== 0 is a pigeonhole check — every card must land in exactly one group, so the total count has to divide evenly. Fails fast, O(1).
The for loop that finds minIdx re-scans the entire remaining working array from scratch, every single time a group starts.
working.indexOf(need) is another full linear scan, and working.splice(idx, 1) shifts every element after idx down by one — both O(n), called groupSize - 1 times per group.
The moment any required consecutive value is missing (idx === -1), the whole function bails out immediately — there’s no “try a different grouping” fallback, because (as the interview corner below explains) there isn’t a better alternative to fall back to.

Complexity

Time	Space	Approach
O(n²)	O(n)	Same greedy order, but every scan/removal is a fresh O(n) pass over a plain array

Solution 2: Optimal — greedy over a sorted frequency map

Count how many of each card value you have in a frequency map, then look at the distinct values in ascending order. The smallest value with a remaining count > 0 is forced to start new run(s) — nothing smaller is left in the hand to precede it. Consume one copy of that value’s count from each of the next groupSize - 1 values immediately; if any of them doesn’t have enough copies, fail right away.

hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3 — same example as Solution 1 (expected: true). Bars are the distinct sorted values; height = remaining count.

Press play to run the optimal frequency-map algorithm.

Step 0 / 9

The code

function isNStraightHandOptimal(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 = Array.from(count.keys()).sort((a, b) => a - b);

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

Line by line:

The frequency map is built once — O(n) — then only the distinct values get sorted, not the whole hand. Duplicates of the same value are handled together via need, not sorted individually.
if (need > 0) skips any value already fully consumed by an earlier, smaller run — without this check the loop would try to re-start runs from cards that don’t exist anymore.
The inner for (let k = 0; k < groupSize; k++) loop consumes need copies of value, value+1, ..., value+groupSize-1 all at once — that’s need whole groups processed in one pass, not one group at a time.
if (have < need) return false fails the instant any consecutive value can’t cover what’s demanded — no backtracking, because the greedy choice that got us here was forced, not a guess (see interview corner).

Complexity

Time	Space	Approach
O(n log n)	O(n)	Frequency map + sort of distinct values, each count consumed in O(1) amortized per group

Complexity comparison

Solution	Time	Space
Brute force (linear scan + indexOf/splice)	O(n²)	O(n)
Optimal (sorted frequency map)	O(n log n)	O(n)

Both implement the exact same greedy rule — always start a run at the smallest remaining card. The difference is purely the data structure: a plain array forces every “find” and “remove” to be a fresh O(n) scan, while a sorted frequency map turns “remove one copy of a value” into an O(1) map update, paying the sort cost only once, up front, over distinct values instead of the whole hand.

Interview corner

Why check hand.length % groupSize !== 0 before doing any real work?

Every card ends up in exactly one group of size groupSize, so the total card count must be an exact multiple of groupSize — a pigeonhole argument, not a heuristic.
If it doesn’t divide evenly, no grouping can possibly exist, full stop.
Checking this first is O(1) and short-circuits every guaranteed-impossible input before touching the (potentially large) frequency map or sort.

Why is it always correct to start a new run at the smallest remaining card, instead of trying other starting points?

Whatever group the smallest remaining card ends up in, it has to be the lowest member of that group — every other member of a consecutive run is strictly larger.
Since nothing smaller is left in the hand, no group could possibly need this card to come after something else — it can only ever be a run’s starting value.
That makes the greedy choice forced, not a guess: there’s no alternative grouping that keeps this card out of a run starting exactly here.

Why does the optimal solution consume need copies at once instead of peeling off one group at a time?

If a value has need copies remaining, all need of them must simultaneously start need separate runs — there’s no other place for those extra copies to go.
Processing them together (one pass over value..value+groupSize-1, subtracting need from each count) is equivalent to running the single-run logic need times, but only touches each distinct value once.
That’s what keeps the total work bounded by the number of distinct values times groupSize, rather than the number of individual cards times groupSize.

Trick question — what does this log?

const counts = {};
counts[100] = 'a';
counts[7] = 'b';
counts[50] = 'c';
console.log(Object.keys(counts));

Answer: ['7', '50', '100'] — NOT insertion order ['100', '7', '50'].
Plain objects treat non-negative integer-like keys as special “array index” keys and always enumerate them in ascending numeric order first, regardless of the order they were assigned.
A real Map (like count in the solution above) has no such rule — it always preserves insertion order, for any key type.
⚠ Trap: this is exactly why the optimal solution above explicitly calls .sort((a, b) => a - b) on sortedValues instead of assuming any implicit ordering — relying on an object’s accidental numeric-key ordering would be undocumented behavior to depend on, and it silently stops applying once a key is no longer a valid array-index integer (e.g. negative numbers, or values ≥ 2³²-1).

Quiz

1. Why does the optimal solution check hand.length % groupSize !== 0 before building the frequency map at all?

Every card must land in exactly one group of size groupSize, so the total card count has to be an exact multiple of groupSize. If it isn’t, no valid grouping can exist no matter what — an O(1) check that rules out guaranteed-impossible inputs immediately.

2. Why must the smallest remaining card (with count > 0) always start a brand-new run?

It can only ever be the lowest member of its group, since nothing smaller than the current minimum is left in the hand. So starting a run there is forced, not a guess.

3. Why does the optimal solution sort only the DISTINCT card values (sortedValues), not the entire hand array?

Duplicates of the same value are handled together via their count, so sorting them individually would be wasted comparison work.

4. The brute-force solution implements the exact same greedy rule as the optimal one. What actually makes it O(n²) instead of O(n log n)?

It re-scans the working array from scratch for every minimum search, and again for every indexOf/splice — O(n) work repeated O(n) times.

5. When a required consecutive value is missing partway through building a run, why can both solutions return false immediately instead of trying a different grouping?

The run’s starting card was a forced choice, not a guess — if it can’t complete, no other valid grouping existed either.