DSA Tracker

Visualize

Hand of Straights

The smallest card left is never free to choose

time O(n log n)space O(n)

There is no real choice to make here, which is why one greedy pass settles it. Look at the smallest card still in hand: nothing smaller exists, so no group can ever place it in the middle or at the top of a run — it has to be the bottom of its own group, and that fixes the other cards that group needs. Take them if they exist; if any is missing the hand is impossible, because that smallest card had no other home to move to. Repeat and the hand either empties or contradicts itself. The duplicate 2 and 3 are the point: after 1,2,3 is spent the smallest card is 2 again, not 4, so the second group starts back down at 2.

Details

Animated on: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3. Can the whole hand be split into groups of 3 consecutive cards?

Problem:Hand of StraightsMedium

The smallest card left is never free to choose

step 1 / 11

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

Sorted hand: 1, 2, 2, 3, 3, 4, 6, 7, 8. 9 cards and a group size of 3, so exactly 3 straights have to come out with nothing left over. Sorting is what makes "smallest card still in hand" cheap to ask, over and over.

Pseudocode
1FUNCTION isNStraightHand(hand, W)
2  IF LENGTH(hand) MOD W != 0
3    RETURN FALSE
4  count <- TALLY(hand)
5  WHILE SIZE(count) > 0
6    low <- MIN(KEYS(count))
7    FOR v <- low TO low + W - 1
8      IF count[v] = 0
9        RETURN FALSE
10      count[v] <- count[v] - 1
11  RETURN TRUE

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Sorted hand: 1, 2, 2, 3, 3, 4, 6, 7, 8. 9 cards and a group size of 3, so exactly 3 straights have to come out with nothing left over. Sorting is what makes "smallest card still in hand" cheap to ask, over and over.
  2. 1 is the smallest card left, and no 0 remains in hand to sit beneath it — so 1 can only ever be the BOTTOM of a straight. That leaves no choice at all: this group must be 1,2,3. Spend one 1.
  3. The group needs 2 next and 2 copies are in hand, so spend one — 1 left of that value. Group so far: 1,2.
  4. 3 was there too, so group 1 closes as 1,2,3 — 6 cards still unspent.
  5. 2 is the smallest card left, and no 1 remains in hand to sit beneath it — so 2 can only ever be the BOTTOM of a straight. That leaves no choice at all: this group must be 2,3,4. Spend one 2. Note that the smallest left fell back to 2 instead of climbing past 3 — the spare copy of 2 has nothing beneath it either, so it opens a group rather than joining one.
  6. The group needs 3 next and 1 copy is in hand, so spend one — 0 left of that value. Group so far: 2,3.
  7. 4 was there too, so group 2 closes as 2,3,4 — 3 cards still unspent.
  8. 6 is the smallest card left, and no 5 remains in hand to sit beneath it — so 6 can only ever be the BOTTOM of a straight. That leaves no choice at all: this group must be 6,7,8. Spend one 6.
  9. The group needs 7 next and 1 copy is in hand, so spend one — 0 left of that value. Group so far: 6,7.
  10. 8 was there too, so group 3 closes as 6,7,8 — 0 cards still unspent.
  11. Every card is spent and each group came out consecutive: [1,2,3] [2,3,4] [6,7,8]. The greedy never had a decision to reconsider, so one pass is the whole proof — the hand CAN be rearranged.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Hand of Straights in the editorAll Greedy problemsBack to roadmap