Hand of Straights

Medium20–25 min

Topics

HashMapGreedySortingArray

Companies

AmazonGoogleBloomberg

You're holding a hand of cards, each showing an integer, and want to split them into groups where every group has exactly groupSize cards forming a run of consecutive integers, with no repeats inside a single group. Determine whether such a split is possible using every card in the hand exactly once.

Test Case 1:

Input:hand = [5, 6, 7, 5, 6, 7], groupSize = 3

Output:true

Explanation:Split into two runs: {5, 6, 7} and {5, 6, 7}.

Test Case 2:

Input:hand = [9, 10, 11, 12], groupSize = 3

Output:false

Explanation:4 cards can't split evenly into groups of 3.

Test Case 3:

Input:hand = [2, 2, 3, 3, 4, 4], groupSize = 2

Output:false

Explanation:Pairing off the 2s and 3s as {2, 3}, {2, 3} leaves two 4s with no 5 to pair with.

Constraints

◆1 ≤ hand.length ≤ 40
◆-100 ≤ hand[i] ≤ 100
◆1 ≤ groupSize ≤ hand.length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Repeated Linear Scan

Good

Sort a working copy of the hand. Repeatedly take the smallest card that hasn't been placed yet as the start of a new group, then scan the entire array to find and claim one copy each of start+1, start+2, ... up to groupSize-1 more cards. If any required value can't be found, no valid grouping exists. This mirrors the process of physically sorting and dealing out runs, but every "find the next needed card" is a fresh linear scan, so the total work grows with the square of the hand size.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) return false;
        int[] sorted = hand.clone();
        Arrays.sort(sorted);
        boolean[] used = new boolean[n];
        int groups = n / groupSize;
        for (int g = 0; g < groups; g++) {
            int j = 0;
            while (used[j]) j++;
            int start = sorted[j];
            used[j] = true;
            for (int i = 1; i < groupSize; i++) {
                int need = start + i;
                int k = -1;
                for (int m = 0; m < n; m++) {
                    if (!used[m] && sorted[m] == need) { k = m; break; }
                }
                if (k == -1) return false;
                used[k] = true;
            }
        }
        return true;
    }
}

Optimal — HashMap Frequency + Greedy Consecutive Runs

Optimal

Count how many times each value appears with a hash map. Walk the distinct values in ascending order; whenever a value v still has c > 0 copies left, those c copies must each be the start of a group (nothing smaller remains to extend a group into v), so v, v+1, ..., v+groupSize-1 must each have at least c copies available right now — subtract c from every one of them in one shot. If any of those values doesn't have enough copies, no valid grouping exists. Because every value's remaining count is looked up directly instead of re-scanned, the only real cost is sorting the distinct values once.

TimeO(n log n)