Difficulty: MediumGreedy

Hand of Straights

Problem in Plain English

Given card values and a group size, decide whether the hand splits into groups of that size where each group holds consecutive values. Every card must be used exactly once.

Problem Statement

Alice holds cards with values hand[i] and wants groups of exactly groupSize cards where each group is a run of consecutive values. Return true when the whole hand splits into such groups, and false otherwise.

For hand = [1, 2, 3, 6, 2, 3, 4, 7, 8] with groupSize = 3 the answer is true via [1,2,3], [2,3,4], and [6,7,8]. For hand = [1, 2, 3, 4, 5] with groupSize = 4 the answer is false because five cards cannot fill groups of four.

Constraints

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

Examples

Example 1

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

The hand splits into [1,2,3], [2,3,4], and [6,7,8].

Example 2

Input: hand = [1, 2, 3, 4, 5], groupSize = 4
Output: false

Each group would use four cards, but five is not a multiple of four. One card would remain regardless of the arrangement, so return false.

Example 3

Input: hand = [1, 1, 2, 2, 3, 4], groupSize = 3
Output: false

The size is divisible by three, but both copies of the smallest value 1 must start [1,2,3]. There are two copies of 2 and only one 3, so the second group cannot be completed. The 4 cannot replace the missing 3.

Example 4

Input: hand = [0], groupSize = 1
Output: true

A group of size one is already a consecutive run. The single card forms [0], so every card is used exactly once.

Intuition

Imagine laying the remaining cards in sorted order. The smallest remaining value cannot appear after another card in a group: that would require an even smaller remaining value. It must start a run. In Example 1, the only 1 forces [1,2,3]; the remaining 2 then forces [2,3,4]. Duplicate values are separate cards, so overlapping runs are allowed but reusing a card is not. This forced-start rule lets us make a greedy choice without guessing between partitions.

Approaches

Sort And Rescan

Solution Details

Reveal Sort And Rescan: intuition, complexity, and code

Intuition

Sort the hand so each group can be assembled left to right: take the first unused card as a group opener and scan forward for its consecutive partners. Marking cards used keeps every card in exactly one group, but each opener can rescan the whole hand.

Step-by-Step Logic

Reject a length that is not divisible by groupSize; otherwise sort a copy and allocate one used flag per card. Example 1 has 9 % 3 = 0 and sorted values [1,2,2,3,3,4,6,7,8].
At each unused position, open a group with that smallest remaining card and set found = 1. In Example 1, index 0 starts at 1.
Scan later positions, accepting only an unused card equal to start + found. Skip duplicates of an already accepted value and previously used positions. The first group accepts indices 1 and 3, making [1,2,3].
If the scan ends before found = groupSize, return false; otherwise resume the outer loop. The next unused index 2 accepts indices 4 and 5, making [2,3,4].
Repeat until no unused position remains. Index 6 starts [6,7,8], all nine flags become true, and Example 1 returns true.

Why It Works

At each outer-loop iteration, the first unused sorted card is the smallest remaining card. Any valid partition of the remaining cards must start a group there, because no smaller card remains to precede it. Scanning rightward finds one unused copy of each required next value; all possible copies of a larger value occur to the right in sorted order. Equal-valued copies are interchangeable, so choosing the first available copy cannot rule out a valid remainder. Used flags prevent reuse. If any required value is missing, the forced group is impossible and no valid partition exists. Otherwise we remove a complete group and apply the same argument to the remainder. Divisibility and completion ensure that returning true consumes every card in a group of exactly the requested size.

Dry Run

Sort And Rescan: variable states at each step
event	start / target	found	used indices after event
sort and guard	`9 % 3 = 0`	not initialized	`[]`
open at i=0	`start=1`, target `2`	initialize `1`	`[0]`
accept j=1	`2`, next target `3`	`1 → 2`	`[0,1]`
skip j=2	value `2` differs from target `3`	`2`	`[0,1]`
accept j=3	`3`, first group complete	`2 → 3`	`[0,1,3]`
skip used i=1; open i=2	`start=2`, target `3`	initialize `1`	`[0,1,2,3]`
skip used j=3; accept j=4	`3`, next target `4`	`1 → 2`	`[0,1,2,3,4]`
accept j=5	`4`, second group complete	`2 → 3`	`[0,1,2,3,4,5]`
skip used i=3,4,5; open i=6	`start=6`, target `7`	initialize `1`	`[0,1,2,3,4,5,6]`
accept j=7	`7`, next target `8`	`1 → 2`	`[0,1,2,3,4,5,6,7]`
accept j=8; skip used i=7,8	`8`, all cards grouped	`2 → 3`	`[0,1,2,3,4,5,6,7,8]`; return `true`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the number of cards. Sorting costs O(n log n). At most n/groupSize groups each scan at most n positions, giving O(n^2) overall; many duplicate pairs can force repeated long scans. The copied hand and used flags both contain n entries, and sorting may also use O(n) temporary storage. Auxiliary space is O(n); the caller's hand is preserved in all three languages.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public boolean isNStraightHand(int[] hand, int groupSize) {5        if (hand.length % groupSize != 0) {6            return false;7        }8        hand = hand.clone();9        Arrays.sort(hand);10        boolean[] used = new boolean[hand.length];11        for (int i = 0; i < hand.length; i++) {12            if (used[i]) {13                continue;14            }15            // The smallest unused card must start its own group.16            int start = hand[i];17            used[i] = true;18            int found = 1;19            for (int j = i + 1; j < hand.length && found < groupSize; j++) {20                // found is the number consumed; start + found is the next value.21                if (!used[j] && hand[j] == start + found) {22                    used[j] = true;23                    found++;24                }25            }26            if (found < groupSize) {27                return false;28            }29        }30        return true;31    }32}

Hints

Hint 1

Ask which card the smallest remaining card must sit beside in its group.

Hint 2

Count copies of each value so repeats stop being special cases.

Hint 3

Always open the next group at the current minimum and demand the following consecutive values in the same quantity.

Edge Cases

A nondivisible length fails before sorting or allocating grouping state, such as five cards with groups of four.
groupSize = 1 always succeeds; [0] is the smallest allowed hand.
Repeated complete runs such as [1,1,2,2,3,3] with size three succeed by creating two groups at once in the count sweep.
Divisibility alone is insufficient: [1,1,2,2,3,4] with size three lacks the second 3.
Gaps between separate completed groups are allowed: [1,2,7,8] with size two succeeds; a gap inside a forced group fails.
Values near 10^9 still require exact successors. A hand of repeated 10^9 values fails for size two; there is no wraparound successor.

Common Mistakes and Interview Tips

Treating duplicate values as one card loses multiplicity; [1,1,2,2,3,3] needs two copies of every member.
Using the first group's starting count directly after decrementing it makes need become zero. Snapshot need before consuming any member.
Grouping adjacent chunks of the sorted array fails when valid groups overlap: Example 1 needs two overlapping runs, not the first sorted chunk [1,2,2].
Using JavaScript's default lexicographic sort visits 10 before 2; always supply (a, b) => a - b.
Returning true after checking only the length misses frequency shortages. Every forced successor must actually exist in sufficient quantity.
Calling an in-place sort on the caller's hand unexpectedly mutates input. Sort a clone or a fresh list of keys as these snippets do.

Key Takeaway

When items must form consecutive runs, the remaining minimum dictates the next group, so count frequencies and build upward from it.