Problem 33.10 · Greedy AlgorithmsMedium

Hand of Straights

What it teaches: The smallest remaining card must start a group, so build groups from it.

Practise it on judges as “Hand of Straights”.

The problem

Return true if the cards can be rearranged into groups of groupSize consecutive values.

Example 1

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

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

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Consecutive groups
→ Forced choice at the smallest value

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	hand = [1,2,3,6,2,3,4,7,8] groupSize = 3	true
2	hand = [1,2,3,4,5] groupSize = 4	false

From slow to fast

Approaches

1. TreeMap counts · O(n log n)

TreeMap counts

Time O(n log n) Space O(n)

While cards remain: first = smallest key; for v in first..first + size − 1, decrement (fail if missing).

Approach 1

import java.util.*;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        TreeMap<Integer, Integer> count = new TreeMap<>();
        for (int c : hand) count.merge(c, 1, Integer::sum);
        while (!count.isEmpty()) {
            int first = count.firstKey();
            for (int v = first; v < first + groupSize; v++) {
                Integer c = count.get(v);
                if (c == null) return false;
                if (c == 1) count.remove(v); else count.put(v, c - 1);
            }
        }
        return true;
    }
}

Verdict: The forced smallest choice is the proof.

Before you submit

Edge cases and common mistakes

Test these inputs

n not divisible by groupSize
groupSize = 1

Mistakes people make

Starting groups from arbitrary cards.

Interview

Follow-up questions

Can it be faster when many duplicates exist?

Command Palette

The problem

Approaches

TreeMap counts

Edge cases and common mistakes

Follow-up questions