Log inSign up
mediumLeetCodeNot Started

Hand of Straights

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

Given an array hand representing card values and an integer groupSize. You must partition all cards into groups of size groupSize such that each group contains groupSize consecutive cards (e.g. [1, 2, 3] or [4, 5, 6]).

Return true if you can partition the hand into valid groups, otherwise return false.

Example 1 · Example 1: Valid Partition:

Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
Output: true
Explanation: Hand can be arranged as [1, 2, 3], [2, 3, 4], [6, 7, 8]. All groups have size 3 and consecutive numbers.

Example 2 · Example 2: Invalid Partition:

Input: hand = [1, 2, 3, 4, 5], groupSize = 4
Output: false
Explanation: Total length is 5, which is not divisible by 4. Impossible to partition.

Constraints:

  • 1 <= hand.length <= 104
  • 0 <= hand[i] <= 109
  • 1 <= groupSize <= hand.length

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why the minimum available card must anchor a consecutive sequence.
  • Implement the frequency-map greedy deduction algorithm.
  • Analyze the difference between BST Map and Hash Map approaches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition an array into groups of fixed size k.
  • Elements in each group must form an unbroken consecutive sequence.
  • All elements must be used.

Algorithmic Decision Tree:

  • Length divisibility check first (n % groupSize == 0).
  • Use a frequency map + ordered keys.
  • Anchor groups on the smallest remaining key.

Connected Patterns:

Divide Array in Sets of K Consecutive NumbersTop K Frequent ElementsGroup Anagrams

1. Brute Force — Quadratic Search with Used Array

Intuition

Sort hand. For each card i from 0 to N - 1: if used[i], continue. We need cards hand[i] + 1, hand[i] + 2, ..., hand[i] + groupSize - 1. Scan forward to find each consecutive card, marking them used. If any is missing, return false.

When to apply: When N <= 200.

Algorithm

  1. Step 1: If hand.length % groupSize != 0 return false.
  2. Step 2: Sort hand ascending.
  3. Step 3: Create boolean used array of size N.
  4. Step 4: For each i: if !used[i], mark used[i] = true and find next groupSize - 1 consecutive cards.
  5. Step 5: If all found, return true; else false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 bool isNStraightHand(vector<int>& hand, int groupSize) {
10 int n = hand.size();
11 if (n % groupSize != 0) return false;
12
13 sort(hand.begin(), hand.end());
14 vector<bool> used(n, false);
15
16 for (int i = 0; i < n; ++i) {
17 if (used[i]) continue;
18 used[i] = true;
19 int needed = hand[i] + 1;
20 int count = 1;
21
22 for (int j = i + 1; j < n && count < groupSize; ++j) {
23 if (!used[j] && hand[j] == needed) {
24 used[j] = true;
25 needed++;
26 count++;
27 }
28 }
29 if (count < groupSize) return false;
30 }
31 return true;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
38 cout << (sol.isNStraightHand(hand, 3) ? "true" : "false") << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops scanning forward for consecutive elements.
  • Space complexity: O(N) — Boolean used array of size N.

Why Brute Force Doesn't Scale:

With N = 104, N2 is 108 operations. Hash map + sorted keys batch decrement reduces it to O(N log N) in ~10ms.

For N = 10,000: O(N log N) requires ~1.4 * 105 operations, executing in ~4ms.

2. Better — Sorted Map / TreeMap Frequency Count

Intuition

Store card counts in a balanced BST map (std::map or TreeMap). While the map is not empty, get the minimum key x. Loop k from 0 to groupSize - 1: if count of x + k is missing or 0, return false. Decrement frequency of x + k, removing keys when frequency reaches 0.

When to apply: When an ordered map data structure is readily available.

Algorithm

  1. Step 1: If hand.length % groupSize != 0 return false.
  2. Step 2: Insert all cards into TreeMap.
  3. Step 3: While map not empty: minKey = map.firstKey().
  4. Step 4: For i from 0 to groupSize - 1: if map doesn't contain minKey + i, return false.
  5. Step 5: Decrement map[minKey + i], remove if 0.
  6. Step 6: Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <map>
4
5using namespace std;
6
7class Solution {
8public:
9 bool isNStraightHand(vector<int>& hand, int groupSize) {
10 if (hand.size() % groupSize != 0) return false;
11
12 map<int, int> count;
13 for (int card : hand) count[card]++;
14
15 while (!count.empty()) {
16 int first = count.begin()->first;
17 for (int i = 0; i < groupSize; ++i) {
18 int card = first + i;
19 if (count.find(card) == count.end()) return false;
20 count[card]--;
21 if (count[card] == 0) count.erase(card);
22 }
23 }
24 return true;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
31 cout << (sol.isNStraightHand(hand, 3) ? "true" : "false") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log U) — TreeMap insertions and deletions take O(log U) per card, where U is unique cards.
  • Space complexity: O(U) — TreeMap holds U unique cards.

3. Optimal — Hash Map + Sorted Unique Keys

Intuition

Count frequencies with a hash map. Extract and sort unique keys ascending. For each key, if count[key] > 0, it must be the start of count[key] groups. Subtract count[key] from all cards key, key + 1, ..., key + groupSize - 1. If any card has insufficient count, return false. Runs in O(N log N) sort time with O(1) hash map operations.

When to apply: Always for Hand of Straights.

Algorithm

  1. Step 1: If hand.length % groupSize != 0 return false.
  2. Step 2: Build frequency map of all cards.
  3. Step 3: Extract unique cards and sort them in ascending order.
  4. Step 4: For each card: if freq = count[card] > 0, verify and decrement count[card + i] by freq for i = 0 to groupSize - 1.
  5. Step 5: Return true if all cards successfully decremented.

Interactive Trace for Hand of Straights

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Check hand
Visual state
Values and pointers at this exact step
pointers
S
used
remaining: 1
remaining: 1
remaining: 1
0
↑ Group 1: [1, 2, 3]
1
2
3
Check / comparison
6 % 3 == 0 (Valid size)
Decision / next transition
Start first straight with minimum card 1.
Why this step matters

Step 1: Check hand.length = 6 % 3 == 0. Build frequencies: {1: 1, 2: 2, 3: 2, 4: 1}.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 bool isNStraightHand(vector<int>& hand, int groupSize) {
11 int n = hand.size();
12 if (n % groupSize != 0) return false;
13
14 unordered_map<int, int> count;
15 for (int card : hand) count[card]++;
16
17 vector<int> uniqueKeys;
18 for (const auto& pair : count) uniqueKeys.push_back(pair.first);
19 sort(uniqueKeys.begin(), uniqueKeys.end());
20
21 for (int card : uniqueKeys) {
22 int freq = count[card];
23 if (freq > 0) {
24 for (int i = 0; i < groupSize; ++i) {
25 int nextCard = card + i;
26 if (count[nextCard] < freq) return false;
27 count[nextCard] -= freq;
28 }
29 }
30 }
31 return true;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
38 cout << (sol.isNStraightHand(hand, 3) ? "true" : "false") << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting unique keys takes O(U log U) <= O(N log N). Hash map operations are O(1).
  • Space complexity: O(N) — Hash map and unique keys list store at most N elements.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Quadratic Array Scan with Used ArrayO(N^2)O(N)Sort hand. For each unused card, scan forward N elements to find the consecutive sequence card+1, card+2, etc., marking them used.Repeated linear scans.
2.Better — TreeMap / Balanced BST Frequency CountO(N log U)O(U) unique keysInsert cards into a sorted map. Repeatedly inspect the first key, decrementing frequencies of the consecutive sequence in O(log U) time.Tree rebalancing overhead.
3.Optimal — Hash Map + Sorted Unique KeysOptimalO(N log N)O(N)Count card frequencies with a Hash Map. Sort unique keys. For each key with count > 0, subtract count from the next groupSize - 1 consecutive numbers.Sorting unique keys.

Common Pitfalls & Crucial Edge Cases

Forgetting length divisibility check

Checking hand.length % groupSize != 0 upfront saves execution time.

Decrementing by 1 instead of by full frequency

If a card has count 5, it forms 5 straights simultaneously; batch decrementing avoids looping 5 times.

Crucial Edge Cases to Validate:

  • groupSize = 1 — Every single card forms a valid group; always returns true.
  • hand.length % groupSize != 0 — Impossible to partition; returns false.
  • All cards identical — Only possible if groupSize == 1; otherwise returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the anchor property: 'The minimum element cannot be preceded by anything, so it must start a group.'
  2. Mention that this exact same problem is LeetCode 1296 (Divide Array in Sets of K Consecutive Numbers).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the smallest remaining card ALWAYS have to be the start of a group?

Back to DSA Sheet