Hand of Straights LeetCode 846 Guide

LeetCode 846 Hand of Straights gives you an array of integers representing a hand of cards and an integer groupSize. Your goal is to determine whether you can rearrange all the cards into groups where each group has exactly groupSize consecutive cards.

For example, hand = [1,2,3,6,2,3,4,7,8] with groupSize = 3 can be split into [1,2,3], [2,3,4], and [6,7,8] — three consecutive groups of size 3, so the answer is true. If groupSize = 2 and the hand has an odd total of cards, the answer is immediately false.

This problem sits at the intersection of greedy algorithms and frequency counting. Sorting the unique card values and consuming them greedily from the smallest produces an elegant O(n log n) solution that avoids backtracking entirely.

The greedy insight is straightforward: always start a new group from the smallest card currently available. The smallest card cannot be in the middle or end of a group — it has no smaller neighbor to precede it. Therefore it must begin some group, and we should form that group immediately.

Once we commit to starting a group at value v, we need one copy each of v, v+1, v+2, ..., v+groupSize-1. If any of those values is missing or fully consumed, the arrangement is impossible and we return false. If they all exist we decrement their counts and continue to the next smallest available card.

This greedy choice is safe because the smallest card has a unique forced role: it must be a group leader. Deferring that role to a later step cannot help — the card will still need to start a group at some point, and acting on it now never invalidates future decisions.

Build a frequency counter from the hand array. Then collect the sorted unique values. Iterate through these unique values in ascending order. For each value v whose count is still greater than zero, you must form exactly count[v] groups starting at v — one group for every remaining copy of v.

For each such group, decrement count[v], count[v+1], ..., count[v+groupSize-1] by the same amount (count[v]). If any of those counts would go negative, the hand cannot be arranged validly; return false immediately.

After processing all unique values, if no step triggered an early false return, all cards have been consumed into valid groups and you return true. The time complexity is O(n log n) for sorting plus O(n * groupSize) for the greedy sweep, with O(n) space for the counter.

The correctness argument relies on the forced role of the minimum element. At every step, the globally smallest card with a positive count has no smaller neighbor available. It cannot participate in any group unless it is the leftmost element of that group. Delaying its consumption would only lead to the same forced choice later with potentially fewer remaining cards to pair it with.

Forming all required groups starting at the current minimum simultaneously — consuming count[v] groups at once — is equivalent to processing them one by one. The order within a batch does not matter because all groups in a batch have identical structure.

If at any point a required successor card v+k has been exhausted (count[v+k] < needed), no rearrangement can supply the missing cards. Cards are fixed; the greedy failure is a true impossibility, not a missed branch.

Consider hand = [1,2,3,6,2,3,4,7,8] with groupSize = 3. First, count frequencies: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}. Total cards = 9, which is divisible by 3, so we proceed.

Sorted unique values: [1, 2, 3, 4, 6, 7, 8]. Process v=1: count[1]=1, form 1 group [1,2,3]. Decrement counts: {1:0, 2:1, 3:1, 4:1, 6:1, 7:1, 8:1}. Process v=2: count[2]=1, form 1 group [2,3,4]. Decrement: {2:0, 3:0, 4:0, 6:1, 7:1, 8:1}.

Process v=3: count[3]=0, skip. Process v=4: count[4]=0, skip. Process v=6: count[6]=1, form 1 group [6,7,8]. Decrement: {6:0, 7:0, 8:0}. All counts reach zero — return true.

In Python, use collections.Counter for frequencies and sorted() on its keys. The loop is a single pass over sorted unique keys: for each key with a positive count, iterate groupSize steps decrementing counts. If any goes negative raise False. Time complexity O(n log n + n*W) where W = groupSize, space O(n).

In Java, use a TreeMap<Integer, Integer> which maintains keys in sorted order, eliminating the need for an explicit sort step. Iterate entrySet(), and for each entry with a positive value, decrement a window of groupSize successive keys. TreeMap.getOrDefault handles missing keys cleanly.

Both implementations benefit from the early-exit check: if hand.length % groupSize != 0, immediately return false before building any data structures. This eliminates an entire class of impossible inputs in O(1).

Hand of Straights belongs to the greedy grouping family. Gas Station (LeetCode 134) uses greedy candidate resets to find the unique valid start in a circular route — the same pattern of committing locally and skipping provably invalid candidates. Task Scheduler (LeetCode 621) greedily fills idle slots to minimize total execution time.

Minimum Rounds to Complete All Tasks (LeetCode 2244) groups identical tasks into batches of 2 or 3, a simpler variant of the consecutive-grouping structure here. Non-Overlapping Intervals (LeetCode 435) uses greedy sorting by end time to minimize interval removals, the same principle of consuming the most constrained element first.

Mastering the sorted-counter greedy pattern in Hand of Straights gives you the template for any problem where you must partition elements into structured groups and the minimum element has a forced role that makes greedy choices provably correct.