LeetCode · #846

Hand of Straights Solution

Given hand of cards, determine if you can rearrange them into groups of groupSize consecutive cards.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #846

🏗️

Pattern

Greedy — sorted grouping

Given hand of cards and group size groupSize, return true if you can rearrange them into groups where each group is groupSize consecutive cards.

Example

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

Constraints

• 1 ≤ hand.length ≤ 10⁴ • 0 ≤ hand[i] ≤ 10⁹ • 1 ≤ groupSize ≤ hand.length

Section Two · Approach 1

Sort + Brute Scanning — O(n · groupSize)

Sort the array. Repeatedly find the smallest remaining card and try to form a group of consecutive cards starting from it. Mark used cards.

Problem: Marking used cards in an array is O(n) per group. Use a frequency map (TreeMap/Counter) for O(log n) per operation.

Java — Sort + scan

 class Solution {
public boolean isNStraightHand(int[] hand, int g) {
if (hand.length % g != 0) return false;
        java.util.Arrays.sort(hand);
boolean[] used = new boolean[hand.length];
for (int i = 0; i < hand.length; i++) {
if (used[i]) continue;
int prev = hand[i], cnt = 1; used[i] = true;
for (int j = i+1; j < hand.length && cnt < g; j++) {
if (!used[j] && hand[j] == prev + 1) {
                    used[j] = true; prev = hand[j]; cnt++;
                }
            }
if (cnt < g) return false;
        }
return true;
    }
}

Python — Sort + scan

 class Solution:
def isNStraightHand(self, hand: list[int], g: int) -> bool:
if len(hand) % g: return False
hand.sort()
        used = [False] * len(hand)
for i in range(len(hand)):
if used[i]: continue
prev, cnt = hand[i], 1; used[i] = True for j in range(i+1, len(hand)):
if not used[j] and hand[j] == prev + 1:
                    used[j] = True; prev = hand[j]; cnt += 1 if cnt == g: break if cnt < g: return False return True

Section Three · Approach 2

TreeMap/Counter — O(n log n)

Count frequencies. Process smallest card first. For each smallest card, try to form a group of groupSize consecutive values, decrementing counts. If any needed value is missing, return false.

💡 Mental model: Imagine sorting poker cards on a table by number. Pick the lowest pile. From that number, try to form a run of groupSize consecutive cards by taking one from each pile. If any pile in the run is empty, the hand can't be arranged into straights.

Algorithm

If n % groupSize != 0: return false.
Build a TreeMap (sorted map) of value → count.
While map is not empty: take smallest key start. For i = start to start + groupSize - 1: if count[i] == 0 → false. Else count[i]--; if 0, remove from map.
Return true.

🎯 When to recognize this pattern: "Can you partition numbers into groups of k consecutive values?" Greedy: always start with the smallest available. Also known as LC 1296 (Divide Array in Sets of K Consecutive Numbers — identical problem).

Section Four · Trace

Visual Walkthrough

Trace for hand=[1,2,3,6,2,3,4,7,8], groupSize=3.

Hand of Straights — TreeMap Grouping

Section Five · Implementation

Code — Java & Python

Java — TreeMap

 import java.util.*;
class Solution {
public boolean isNStraightHand(int[] hand, int g) {
if (hand.length % g != 0) return false;
TreeMap<Integer,Integer> map = new TreeMap<>();
for (int c : hand) map.merge(c, 1, Integer::sum);
while (!map.isEmpty()) {
int start = map.firstKey();
for (int i = start; i < start + g; i++) {
if (!map.containsKey(i)) return false;
if (map.get(i) == 1) map.remove(i);
else map.put(i, map.get(i) - 1);
            }
        }
return true;
    }
}

Python — Counter + sorted

 from collections import Counter
class Solution:
def isNStraightHand(self, hand: list[int], g: int) -> bool:
if len(hand) % g: return False
cnt = Counter(hand)
for start in sorted(cnt):
while cnt[start] > 0:
for i in range(start, start + g):
if cnt[i] <= 0: return False
cnt[i] -= 1 return True

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort + scan	O(n · groupSize)	O(n)	Boolean used array
TreeMap/Counter ← optimal	O(n log n)	O(n)	Sorted map; process smallest first

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Not divisible	`[1,2,3], g=2`	3 % 2 ≠ 0 → false immediately.
groupSize = 1	`[5,3,1]`	Every card is its own group. Always true.
Duplicates	`[1,1,2,2,3,3], g=3`	Two groups: [1,2,3] and [1,2,3]. True.
Gap in sequence	`[1,2,4,5], g=2`	[1,2] works, but 4,5 aren't consecutive from 3. Wait — [4,5] is valid. True.
Missing consecutive	`[1,3,5], g=3`	Need 1,2,3 but 2 missing. False.

⚠ Common Mistake: Not always starting from the smallest. If you start from an arbitrary card, you might form a valid group but leave smaller cards stranded. Always greedily start from the smallest available card — it must be the start of a group (no smaller card can precede it).

← Back to Greedy problems

LearningTree

LC 846 · Hand of Straights — Solution & Explanation | DSA Guide