295. Hand of Straights
🔗 LeetCode Problem: 846. Hand of Straights
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Greedy, Sorting
Problem Statement
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.
Constraints:
- 1 <= hand.length <= 10^4
- 0 <= hand[i] <= 10^9
- 1 <= groupSize <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
🌳 Visual Understanding - The Card Grouping Problem
The Problem We're Solving:
Cards: [1, 2, 3, 6, 2, 3, 4, 7, 8]
Group size: 3
Question: Can we form groups of 3 CONSECUTIVE cards?
Sorted: [1, 2, 2, 3, 3, 4, 6, 7, 8]
Try to form groups:
Group 1: [1, 2, 3] ✓ Consecutive!
Group 2: [2, 3, 4] ✓ Consecutive!
Group 3: [6, 7, 8] ✓ Consecutive!
All cards used, all groups valid!
Answer: true ✓
Understanding "Consecutive":
Consecutive means: numbers differ by exactly 1
Valid consecutive groups of size 3:
[1, 2, 3] ✓
[5, 6, 7] ✓
[10, 11, 12] ✓
Invalid groups:
[1, 2, 4] ✗ (gap: 2→4 is 2, not 1)
[1, 3, 5] ✗ (gaps of 2)
[5, 5, 5] ✗ (not consecutive, all same)
Key Observations:
1. MUST use ALL cards
Can't leave any card out
2. Each group has EXACTLY groupSize cards
If total cards not divisible by groupSize → impossible!
3. Cards must be CONSECUTIVE
[n, n+1, n+2, ..., n+groupSize-1]
4. Each card value can be used MULTIPLE times
hand = [1, 1, 2, 2, 3, 3]
Can form: [1,2,3] and [1,2,3] ✓
The Core Challenge:
Given: hand = [1, 2, 2, 3, 3, 4], groupSize = 3
How to approach?
Naive: Try all possible groupings → O(n!) - TOO SLOW!
Better: Use GREEDY approach!
- Start with smallest card
- Try to form consecutive group from it
- Repeat until all cards used or impossible
Why greedy works?
If we have card with value 'x', we MUST use it
Best strategy: Use it in a group starting with smallest available!
🧠 The AHA Moment - Greedy from Smallest
The Key Insight:
Insight: Always start groups with the SMALLEST card available!
Why?
If we have the smallest card (say, value 5):
- It MUST be used in some group
- It can ONLY start a group or follow 4, 3, 2...
- But 4, 3, 2... must be available too!
- Simplest: Start a group with 5!
This greedy choice is ALWAYS valid if solution exists!
Visual Discovery - Why Greedy Works
Example: hand = [1, 2, 2, 3, 3, 4], groupSize = 3
Count frequency:
1 → 1 time
2 → 2 times
3 → 2 times
4 → 1 time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Start with smallest card (1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Card 1 exists (count = 1)
Try to form group: [1, 2, 3]
Need:
1 → available (count = 1) ✓
2 → available (count = 2) ✓
3 → available (count = 2) ✓
Form group [1, 2, 3]!
Update counts:
1 → 0
2 → 1
3 → 1
4 → 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Start with smallest remaining card (2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Card 2 exists (count = 1)
Try to form group: [2, 3, 4]
Need:
2 → available (count = 1) ✓
3 → available (count = 1) ✓
4 → available (count = 1) ✓
Form group [2, 3, 4]!
Update counts:
2 → 0
3 → 0
4 → 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
All counts = 0
All cards used!
Answer: true ✓
Groups formed: [1,2,3], [2,3,4]
Why Starting with Smallest is Optimal
Proof by Contradiction:
Suppose we DON'T start with smallest card.
Example: We have cards [1, 2, 3] but start group with 2.
Group: [2, 3, 4]
Need card 4, but we don't have it!
Also, card 1 is left unused and can't form group!
The smallest card (1) has NO OTHER OPTION:
- Can't be in middle of group (no 0)
- Can't be at end of group (no -1, -2)
- MUST start a group!
Therefore: Always start with smallest! 🎯
The Algorithm Strategy
1. Count frequency of each card value
2. Sort unique card values (or use sorted map)
3. For each card value (smallest first):
If count > 0:
- Try to form group starting with this card
- Need: card, card+1, card+2, ..., card+groupSize-1
- Check if ALL are available
- If YES: decrease their counts
- If NO: return false (impossible)
4. If we process all cards successfully: return true
🟢 Approach: Greedy with Frequency Map (Optimal)
🎨 Building the Complete Solution
Step 1: Why We Need Frequency Count
We can have duplicate cards!
Example: hand = [1, 1, 2, 2, 3, 3]
We need to know:
- How many 1's? (2)
- How many 2's? (2)
- How many 3's? (2)
So we can form: [1,2,3] and [1,2,3] ✓
Use a frequency map: value → count
Step 2: Why We Need Sorted Order
We must process cards in ASCENDING order!
Because greedy strategy: start with smallest
Can't process randomly:
[3, 1, 2] → Wrong order!
[1, 2, 3] → Correct order!
Use TreeMap (Java) or sorted keys
Step 3: The Greedy Algorithm in Detail
For each unique card value (in sorted order):
While this card still has count > 0:
Try to form a group starting with this card:
Need cards: [card, card+1, card+2, ..., card+groupSize-1]
Check availability:
For each needed card:
If count == 0: IMPOSSIBLE! Return false
Decrease counts:
For each needed card:
Decrease count by 1
If we successfully process all cards: Return true
📝 Implementation - Clean and Efficient
import java.util.*;
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
// Edge case: Check if grouping is possible
if (hand.length % groupSize != 0) {
return false; // Can't divide evenly
}
// Step 1: Count frequency using TreeMap (automatically sorted)
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int card : hand) {
count.put(card, count.getOrDefault(card, 0) + 1);
}
// Step 2: Process cards in sorted order (greedy)
for (int card : count.keySet()) {
int freq = count.get(card);
// While this card still needs to be used
while (freq > 0) {
// Try to form a group starting with 'card'
for (int i = 0; i < groupSize; i++) {
int needed = card + i;
int available = count.getOrDefault(needed, 0);
// If needed card not available
if (available == 0) {
return false; // Impossible!
}
// Use this card
count.put(needed, available - 1);
}
freq--;
}
}
return true; // Successfully formed all groups!
}
}
🔍 Complete Dry Run
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Check if possible
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
hand.length = 9
groupSize = 3
9 % 3 = 0 ✓ (evenly divisible)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Build frequency map
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TreeMap (automatically sorted):
1 → 1
2 → 2
3 → 2
4 → 1
6 → 1
7 → 1
8 → 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process each card (sorted order)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
─────────────────────────────────────────────────────────
Process card = 1, freq = 1
─────────────────────────────────────────────────────────
freq > 0? (1 > 0) YES
Form group starting with 1:
Need: 1, 2, 3
Check 1: count[1] = 1 ✓ Available
Check 2: count[2] = 2 ✓ Available
Check 3: count[3] = 2 ✓ Available
Use cards:
count[1] = 0
count[2] = 1
count[3] = 1
freq = 0
freq > 0? NO, done with card 1
─────────────────────────────────────────────────────────
Process card = 2, freq = 1
─────────────────────────────────────────────────────────
freq > 0? (1 > 0) YES
Form group starting with 2:
Need: 2, 3, 4
Check 2: count[2] = 1 ✓ Available
Check 3: count[3] = 1 ✓ Available
Check 4: count[4] = 1 ✓ Available
Use cards:
count[2] = 0
count[3] = 0
count[4] = 0
freq = 0
freq > 0? NO, done with card 2
─────────────────────────────────────────────────────────
Process card = 3, freq = 0
─────────────────────────────────────────────────────────
freq > 0? (0 > 0) NO
Skip (already used in previous groups)
─────────────────────────────────────────────────────────
Process card = 4, freq = 0
─────────────────────────────────────────────────────────
freq > 0? (0 > 0) NO
Skip (already used in previous groups)
─────────────────────────────────────────────────────────
Process card = 6, freq = 1
─────────────────────────────────────────────────────────
freq > 0? (1 > 0) YES
Form group starting with 6:
Need: 6, 7, 8
Check 6: count[6] = 1 ✓ Available
Check 7: count[7] = 1 ✓ Available
Check 8: count[8] = 1 ✓ Available
Use cards:
count[6] = 0
count[7] = 0
count[8] = 0
freq = 0
freq > 0? NO, done with card 6
─────────────────────────────────────────────────────────
Process card = 7, freq = 0
─────────────────────────────────────────────────────────
Skip (already used)
─────────────────────────────────────────────────────────
Process card = 8, freq = 0
─────────────────────────────────────────────────────────
Skip (already used)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
All cards processed successfully!
All counts = 0
Groups formed:
[1, 2, 3]
[2, 3, 4]
[6, 7, 8]
Answer: true ✓
Example of Impossible Case
Input: hand = [1,2,3,4,5], groupSize = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Check if possible
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
hand.length = 5
groupSize = 4
5 % 4 = 1 ✗ (NOT evenly divisible)
Return false immediately!
Explanation: 5 cards can't be divided into groups of 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Another example: hand = [1,2,4,5], groupSize = 2
Check: 4 % 2 = 0 ✓
Frequency:
1 → 1
2 → 1
4 → 1
5 → 1
Process card = 1:
Need: 1, 2
Check 1: count[1] = 1 ✓
Check 2: count[2] = 1 ✓
Form [1, 2] ✓
Process card = 4:
Need: 4, 5
Check 4: count[4] = 1 ✓
Check 5: count[5] = 1 ✓
Form [4, 5] ✓
Answer: true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Yet another: hand = [1,2,3,5], groupSize = 3
Check: 4 % 3 = 1 ✗
Return false!
📊 Complexity Analysis
Time Complexity: O(n log n + n × groupSize)
Building TreeMap: O(n log n)
Processing cards:
- Iterate through unique cards: O(unique)
- For each card's frequency: O(freq)
- Form group: O(groupSize)
- Total: O(n × groupSize) in worst case
Overall: O(n log n + n × groupSize)
Since groupSize is typically small and constant:
Practical: O(n log n)
Space Complexity: O(n)
TreeMap storing unique cards and counts: O(unique) ≤ O(n)
💡 Optimized Implementation - More Efficient
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) return false;
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int card : hand) {
count.put(card, count.getOrDefault(card, 0) + 1);
}
// Process smallest card repeatedly
while (!count.isEmpty()) {
// Get smallest card
int first = count.firstKey();
// Try to form group starting with 'first'
for (int i = 0; i < groupSize; i++) {
int card = first + i;
if (!count.containsKey(card)) {
return false; // Missing card
}
int freq = count.get(card);
if (freq == 1) {
count.remove(card); // Remove if count becomes 0
} else {
count.put(card, freq - 1);
}
}
}
return true;
}
}
This version:
- Uses firstKey() to always get smallest
- Removes cards with count 0 (cleaner map)
- Same logic, slightly more elegant
- Same complexity
🎯 Key Insights Summary
The Three Critical Points:
1. Greedy from Smallest
Always start groups with the SMALLEST available card
Why?
- Smallest card MUST be used
- It can ONLY start a group (no smaller predecessors)
- This choice is always safe if solution exists!
This is the KEY greedy insight! 🔑
2. Frequency Counting
We can have duplicates!
Must track:
- Which card values exist
- How many of each
Use frequency map: TreeMap for sorted order
3. Early Termination Check
If hand.length % groupSize != 0:
→ Impossible to divide evenly
→ Return false immediately!
Saves unnecessary computation! ✓
🎓 Pattern Recognition - Greedy Grouping
Template for Consecutive Grouping Problems
// Pattern: Form consecutive groups greedily
class Solution {
public boolean canFormGroups(int[] array, int groupSize) {
// Early check
if (array.length % groupSize != 0) return false;
// Count frequency (sorted)
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int num : array) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// Greedy: process smallest first
while (!count.isEmpty()) {
int start = count.firstKey();
// Try to form consecutive group
for (int i = 0; i < groupSize; i++) {
int needed = start + i;
if (!count.containsKey(needed)) return false;
int freq = count.get(needed);
if (freq == 1) count.remove(needed);
else count.put(needed, freq - 1);
}
}
return true;
}
}
Related Problems
- Divide Array in Sets of K Consecutive Numbers (LC 1296)
Exact same problem!
- Split Array into Consecutive Subsequences (LC 659)
Similar but subsequences can be longer
- Card Flipping Game (LC 822)
Different constraint but similar grouping
⚠️ Common Mistakes
// Mistake 1: Not checking divisibility first
// ❌ Forgot early check
TreeMap<Integer, Integer> count = new TreeMap<>();
// ✓ CORRECT: Check first
if (hand.length % groupSize != 0) return false;
// Mistake 2: Not using sorted structure
HashMap<Integer, Integer> count = new HashMap<>(); // ❌ Unordered!
// ✓ CORRECT: Use TreeMap for sorted order
TreeMap<Integer, Integer> count = new TreeMap<>();
// Mistake 3: Not handling count = 0 properly
count.put(card, count.get(card) - 1); // ❌ Might go negative!
// ✓ CORRECT: Check and remove if 0
if (freq == 1) count.remove(card);
else count.put(card, freq - 1);
// Mistake 4: Starting from wrong card
for (int card : hand) { // ❌ Unsorted order!
// ✓ CORRECT: Use sorted map keys
for (int card : count.keySet()) {
📝 Quick Revision Notes
🎯 Core Concept
Problem: Form groups of groupSize CONSECUTIVE cards
Key Insight: Greedy - always start groups with SMALLEST card
Algorithm: 1. Check if length divisible by groupSize 2. Count frequency (use TreeMap for sorting) 3. Process smallest card, form consecutive group 4. Repeat until all cards used or impossible
Why Greedy Works: Smallest card MUST start a group!
⚡ Quick Implementation
import java.util.TreeMap;
public class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
return greedy(hand, groupSize);
}
private boolean greedy(int[] hand, int groupSize) {
// Approach: no logic, only observation
// step 1: check feasability (fast fail)
int n = hand.length;
if (n % groupSize != 0) {
return false;
}
// step 2: create freq map (treemap with keys sorted)
// Example: 1, 2, 3, 6, 2, 3, 4, 7, 8
// {1=1, 2=2, 3=2, 4=1, 6=1, 7=1, 8=1}
TreeMap<Integer, Integer> freqMap = new TreeMap<>();
for (int num : hand) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// step 3: loop freq map key set
for (int key : freqMap.keySet()) {
// GOTCHA: do a real-time like below. Not assigning to
// some variable and decrement inside the while loop.
// step 4: we need to keep on pairing with the
// first element until it is available.
// For example, if its {1=2, 2=2, 3=2}
// 2 sets gets formed as {1,2,3}
// We will take first time 1 and group gets formed as
// {1,2,3}. Updated freqMap {1=1, 2=1, 3=1}. Again, same
// while loop with 1 only as starting element.
while (freqMap.get(key) > 0) {
// step 4: whatever number comes, we need to start
// creating group with the asked size.
// For exmaple, if 1 comes from above map, we need to
// check if we can create group of 3 with elements {1,2,3}
for (int i = 0; i < groupSize; i++) {
int num = key + i;
// GOTCHA: NULL check
Integer freq = freqMap.get(num);
if (freq == null || freq == 0) {
return false;
}
if (freq > 0) {
// step 5: reduce its frequency as we considered it
freqMap.put(num, freq - 1);
} else {
// step 6: stop as next consecutive number is not available
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isNStraightHand(new int[] { 1, 2, 3, 6, 2, 3, 4, 7, 8 }, 3) == true);
// System.out.println(s.isNStraightHand(new int[] { 1, 2, 3, 4, 5 }, 4) ==
// false);
}
}
🔑 Key Points
✓ Check divisibility first (early termination)
✓ Use TreeMap (automatic sorting)
✓ Always start with smallest (greedy)
✓ Form consecutive groups (card, card+1, ..., card+k-1)
✓ Time: O(n log n), Space: O(n)
✓ Greedy is optimal
🎪 Memory Aid
"Smallest first, groups we form!"
"Consecutive cards, the norm!"
"TreeMap sorts, keeps us warm!"
"Greedy choice, performs!" ✨
🎉 Congratulations!
You've mastered Hand of Straights!
What You Learned:
✅ Greedy grouping - Start with smallest
✅ Frequency counting - Handle duplicates
✅ Consecutive sequences - Form valid groups
✅ TreeMap usage - Automatic sorting
✅ Early termination - Divisibility check
The Beautiful Insight:
Card Grouping Problem → Simple Greedy Solution
The core insight:
"Smallest card MUST be used"
"It can ONLY start a group"
"Therefore: Always start with smallest!"
This greedy choice:
- Is always safe (if solution exists)
- Simplifies the problem recursively
- Leads to optimal solution!
This is the power of Greedy:
Find the FORCED move (smallest must start)
Make that move confidently
Problem becomes smaller
Recursively solve! 🎯
This pattern appears in:
- Scheduling problems
- Resource allocation
- Sequence formation
Master this pattern = Solve many problems! ✨
Interview Mastery:
When asked about Hand of Straights:
1. Understand: "Form groups of k consecutive cards"
2. Early check: "First verify: length divisible by groupSize?
If not, impossible immediately."
3. Key insight: "Use greedy approach - always start
groups with smallest available card."
4. Why greedy works: "Smallest card MUST be in some group.
It can only start a group (no smaller predecessors).
So starting with it is always optimal!"
5. Data structure: "Use TreeMap to maintain sorted order
and track frequencies."
6. Code it: Clean O(n log n) solution
7. Complexity: "O(n log n) for sorting via TreeMap,
O(n) for processing. Space O(n) for map."
Shows complete understanding! 💯
You've mastered greedy grouping with consecutive sequences! 🚀✨🎯