AlgoViz
HomeHeap / Priority Queue

Hand of Straights

Medium

Always start a group at the smallest card left

Problem

Given cards and a group size, return whether they can be split into groups of consecutive cards of that size.

In simple words

Always start a group from the smallest remaining card, consuming the next consecutive ones.

The idea

The smallest remaining card must begin a group, because nothing smaller can precede it. Remove it and the next groupSize-1 consecutive values; if any is missing, the split is impossible.

The trick

  • Count the cards, then repeatedly consume runs starting at the smallest key.
  • Fail immediately if a required consecutive value is missing.
  • Impossible unless the total count divides by the group size.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
6
2
3
4
7
8
0
1
2
3
4
5
6
7
8

Step 1 of 2. Here's the example — hand=[1,2,3,6,2,3,4,7,8], groupSize=3 Values: 1, 2, 3, 6, 2, 3, 4, 7, 8.

1/2
Optimal
timeO(n log n)spaceO(n)
1count each card2for smallest available card start: try to take card..card+size-1, decrementing counts3fail if any missing

Input

array
[1, 2, 3, 6, 2, 3, 4, 7, 8]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output:
true
Explanation:
Forms [1,2,3],[2,3,4],[6,7,8].

Example 2

Input:
hand = [1,2,3,4,5], groupSize = 4
Output:
false
Explanation:
5 cards can't split into groups of 4 → false.

Example 3

Input:
hand = [1,2,3], groupSize = 3
Output:
true
Explanation:
One straight run.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.