Hand of Straights — Solution in Python, Java & C++
Hand of Straights solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Hand of Straights is a medium coding problem on arrays, hash table and sorting.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Greedy
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Alice has cards with values hand and wants to rearrange them into groups of exactly groupSize consecutive cards. Return true if she can.
Example 1
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: [1,2,3], [2,3,4], [6,7,8].
Example 2
Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Constraints
1 <= hand.length <= 241 <= hand[i] <= 201 <= groupSize <= 6
Hints for Hand of Straights
Hint 1
If groupSize doesn't divide the hand size, it's impossible.
Hint 2
Always start a group at the smallest remaining card — it has no other home.
How to solve Hand of Straights
The smallest remaining card has no freedom: it cannot sit in the middle or at the end of a run, because that would need a smaller card, and none exists. So it must start a group, which forces the whole group. Repeat, and the entire arrangement is determined — no search required.
Approach
- If
hand.lengthis not divisible bygroupSize, returnfalseimmediately. - Count how many of each card value you hold.
- Walk the values in ascending order. Let
cbe the remaining count of the smallest valuevwithc > 0. - Those
ccards must each start a group, so you needccopies ofv+1, v+2, …, v+groupSize-1too. - If any of those is short, return
false; otherwise subtractcfrom each and continue. Surviving the walk meanstrue.
Why it works
The forcing argument makes greedy exact. Because the smallest remaining value can only ever be a group's first card, taking all c copies as group starts is not a choice but a necessity — any valid arrangement must do the same. Each step therefore either matches the unique possibility or proves none exists, so the algorithm never has to backtrack.
Complexity
- Time —
O(n log n + d · groupSize) - Space —
O(d)
Pitfalls
- The divisibility check first — otherwise a leftover partial group slips through.
- Consume all
ccopies at once. Handling one card at a time works but is slower and easier to get wrong. - Values are not contiguous: skip values whose count has already fallen to zero rather than assuming
v+1exists. groupSize = 1makes everything trivially true; the loop must handle it without special-casing.
Reference solution
Python
from typing import List
from collections import Counter
def isNStraightHand(hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize != 0:
return False
count = Counter(hand)
for k in sorted(count):
need = count[k]
if need == 0:
continue
for v in range(k, k + groupSize):
if count[v] < need:
return False
count[v] -= need
return TrueJava
public static boolean isNStraightHand(int[] hand, int groupSize) {
int n = hand.length;
if (n % groupSize != 0) return false;
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int x : hand) count.put(x, count.getOrDefault(x, 0) + 1);
for (int v : new ArrayList<>(count.keySet())) {
int c = count.getOrDefault(v, 0);
if (c == 0) continue;
for (int j = 0; j < groupSize; j++) {
int w = v + j;
int have = count.getOrDefault(w, 0);
if (have < c) return false;
count.put(w, have - c);
}
}
return true;
}C++
bool isNStraightHand(vector<int>& hand, int groupSize) {
int n = (int) hand.size();
if (n % groupSize != 0) return false;
map<int, int> count;
for (int x : hand) count[x]++;
vector<int> values;
for (const auto& e : count) values.push_back(e.first);
for (int v : values) {
int c = count[v];
if (c == 0) continue;
for (int j = 0; j < groupSize; j++) {
int w = v + j;
if (count[w] < c) return false;
count[w] -= c;
}
}
return true;
}JavaScript
var isNStraightHand = function(hand, groupSize) {
if (hand.length % groupSize !== 0) return false;
const count = new Map();
for (const c of hand) count.set(c, (count.get(c) || 0) + 1);
const keys = Array.from(count.keys()).sort(function(a, b) { return a - b; });
for (const k of keys) {
const need = count.get(k) || 0;
if (need === 0) continue;
for (let v = k; v < k + groupSize; v++) {
const have = count.get(v) || 0;
if (have < need) return false;
count.set(v, have - need);
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets