846. Hand of Straights

At a Glance

Topic: greedy
Pattern: Greedy with ordered frequency map
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Apple, Oracle
Frequency: Medium
LeetCode: 846

Problem (one-liner)

Partition multiset of integers into groups of size groupSize so each group forms consecutive values. Return whether a valid partition exists. Input: hand, groupSize. Output: boolean.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Consecutive in each group”
Process from smallest value upward; each starting value uses all remaining copies as parallel group starts
Map counts; sorted iteration or min-heap of active values

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Backtracking — too slow.
Sort + greedy consumption — O(n log n) time / O(n) space. <- pick this in interview.

Optimal Solution

Go

package main

import "sort"

func isNStraightHand(hand []int, groupSize int) bool {
	if len(hand)%groupSize != 0 {
		return false
	}
	sort.Ints(hand)
	counts := make(map[int]int)
	for _, value := range hand {
		counts[value]++
	}
	for _, value := range hand {
		need := counts[value]
		if need == 0 {
			continue
		}
		for offset := 0; offset < groupSize; offset++ {
			card := value + offset
			available := counts[card]
			if available < need {
				return false
			}
			counts[card] = available - need
		}
	}
	return true
}

JavaScript

function isNStraightHand(hand, groupSize) {
	if (hand.length % groupSize !== 0) return false;
	hand.sort((left, right) => left - right);
	const counts = new Map();
	for (const value of hand) {
		counts.set(value, (counts.get(value) ?? 0) + 1);
	}
	for (const value of hand) {
		const need = counts.get(value) ?? 0;
		if (need === 0) continue;
		for (let offset = 0; offset < groupSize; offset++) {
			const card = value + offset;
			const available = counts.get(card) ?? 0;
			if (available < need) return false;
			counts.set(card, available - need);
		}
	}
	return true;
}