126.Hand of Straights

MediumGreedy · 5/8

Problem

Alice has a hand of cards, given as an integer array hand where hand[i] is the value on the i-th card. She wants to rearrange all the cards into groups of exactly groupSize cards, where each group consists of groupSize consecutive values.

Return true if she can do this using every card, otherwise false.

Examples

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].

Input:  hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: 5 cards cannot be split into groups of 4.

Input:  hand = [1,1,2,2,3,4], groupSize = 3
Output: false
Explanation: Both 1s must start a group, needing two 3s, but there is only one.

Constraints

1 <= hand.length <= 10^4
0 <= hand[i] <= 10^9
1 <= groupSize <= hand.length

💡 Key Insight

The smallest remaining card has no smaller neighbour to belong to, so it must start a group. That forces the next groupSize - 1 values. Repeating this greedy choice either consumes every card or hits a missing value, in which case the answer is false. The only question is how to find "the smallest remaining card" efficiently — sorting, a TreeMap, or walking back to the start of each run of consecutive values in a HashMap.

Sort and Scan

TimeO(n²) worst caseSpaceO(n)

Intuition

Sort the hand. The first unused card is the smallest remaining, so it starts a group; scan forward for the next unused cards with values +1, +2, ... and mark them used. If any required value is missing, fail.

Algorithm

If hand.length % groupSize != 0, return false.
Sort hand; used[] all false.
For each unused index i: mark it, set need = hand[i] + 1, and scan j > i for unused cards equal to need, marking them, until the group is complete. If the scan passes a value greater than need or runs out, return false.
Return true.

Visualization

sorted: [1,2,2,3,3,4,6,7,8], groupSize = 3
group from 1: take 1, 2 (idx1), 3 (idx3)       remaining: 2,3,4,6,7,8
group from 2: take 2 (idx2), 3 (idx4), 4       remaining: 6,7,8
group from 6: take 6, 7, 8                     all used -> true

Code

java

import java.util.Arrays;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) {
            return false;
        }
        Arrays.sort(hand);
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true; // smallest remaining card starts a group
            int need = hand[i] + 1;
            int taken = 1;
            for (int j = i + 1; j < n && taken < groupSize; j++) {
                if (used[j] || hand[j] < need) {
                    continue; // used, or a duplicate of an earlier value
                }
                if (hand[j] > need) {
                    return false; // the required value is missing
                }
                used[j] = true;
                need++;
                taken++;
            }
            if (taken < groupSize) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(n²) worst case — each group scan may pass over many used or duplicate cards (plus O(n log n) sort).
Space: O(n) — the used array.

TreeMap of Counts

TimeO(n log n)SpaceO(n)

Intuition

Store value -> count in a TreeMap, which keeps keys sorted. Repeatedly take the smallest key first; it must start count[first] groups at once. For each value first .. first + groupSize - 1, subtract that many copies; if any value has fewer copies, fail.

Algorithm

If n % groupSize != 0, return false.
Count cards in a TreeMap.
While the map is non-empty: first = firstKey(), k = count[first]. For v in first .. first + groupSize - 1: if count[v] < k, return false; else subtract k (remove the key at zero).
Return true.

Visualization

counts: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}
first=1, k=1 -> subtract 1 from 1,2,3  -> {2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
first=2, k=1 -> subtract 1 from 2,3,4  -> {6:1, 7:1, 8:1}
first=6, k=1 -> subtract 1 from 6,7,8  -> {}  -> true

Code

java

import java.util.TreeMap;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        TreeMap<Integer, Integer> count = new TreeMap<>();
        for (int card : hand) {
            count.merge(card, 1, Integer::sum);
        }
        while (!count.isEmpty()) {
            int first = count.firstKey();
            int k = count.get(first); // this many groups must start at `first`
            for (int v = first; v < first + groupSize; v++) {
                int have = count.getOrDefault(v, 0);
                if (have < k) {
                    return false;
                }
                if (have == k) {
                    count.remove(v);
                } else {
                    count.put(v, have - k);
                }
            }
        }
        return true;
    }
}

Complexity

Time: O(n log n) — each distinct value is visited at most groupSize times with O(log n) map operations; in total bounded by the n cards removed.
Space: O(n) — the map.

HashMap with Run StartsOptimal

TimeO(n) amortisedSpaceO(n)

Intuition

We do not need full sorting — only a way to find a valid group start. Given any card num, walk down while num - 1 is still present; the value we stop at is the smallest card in that run of consecutive values, so it must start a group. From that start, carve out groups and move upward until we pass num. Each card is consumed once, and the walk-downs are short because they stop at the first missing value.

Algorithm

If n % groupSize != 0, return false.
Count cards in a HashMap.
For each num in hand:
- start = num; while count[start - 1] > 0, start--.
- While start <= num: while count[start] > 0, consume one group start .. start + groupSize - 1 (fail if any count is 0). Then start++.
Return true.

Dry Run

flowchart TD
    A["num = 1: walk down, 0 absent<br/>start = 1"] --> B["group 1,2,3<br/>counts: 2:1 3:1 4:1 6:1 7:1 8:1"]
    B --> C["start = 2: count 1 -> group 2,3,4<br/>counts: 6:1 7:1 8:1"]
    C --> D["num = 2, 3, 6 ..."]
    D --> E["num = 6: walk down, 5 absent<br/>start = 6 -> group 6,7,8"]
    E --> F["all counts 0 -> return true"]

Code

java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) {
            return false;
        }
        Map<Integer, Integer> count = new HashMap<>();
        for (int card : hand) {
            count.merge(card, 1, Integer::sum);
        }
        for (int num : hand) {
            // walk down to the smallest card in this consecutive run
            int start = num;
            while (count.getOrDefault(start - 1, 0) > 0) {
                start--;
            }
            // form every group that must start between `start` and `num`
            while (start <= num) {
                while (count.getOrDefault(start, 0) > 0) {
                    for (int v = start; v < start + groupSize; v++) {
                        int have = count.getOrDefault(v, 0);
                        if (have == 0) {
                            return false; // gap inside a required group
                        }
                        count.put(v, have - 1);
                    }
                }
                start++;
            }
        }
        return true;
    }
}

Complexity

Time: O(n) amortised — every card is decremented exactly once, and walk-downs only cross values that are still present.
Space: O(n) — the count map.

Complexity Comparison

Approach	Time	Space
Sort and Scan	O(n²)	O(n)
TreeMap of Counts	O(n log n)	O(n)
HashMap with Run Starts	O(n) amortised	O(n)

Common Pitfalls

Skipping the hand.length % groupSize check — it is a free early exit.
Starting a group from an arbitrary card instead of the smallest one in its run; e.g. starting at 2 in [1,2,3,2,3,4] strands the 1.
Forgetting duplicates: when the smallest value appears k times, k groups must start there.
Removing keys from a TreeMap while iterating over its keySet() — this throws ConcurrentModificationException; re-read firstKey() each round instead.