Watch 10 video solutions for Hand of Straights, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by NeetCode has 88,819 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: Alice's hand can not be rearranged into groups of 4.
Constraints:
1 <= hand.length <= 1040 <= hand[i] <= 1091 <= groupSize <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Problem Overview: You receive an array of card values and a group size. The task is to determine whether the cards can be rearranged into groups where each group contains groupSize consecutive integers. Every card must be used exactly once.
Approach 1: Sorting and Greedy (O(n log n) time, O(n) space)
This approach starts by sorting the cards so the smallest available value is always processed first. Maintain a frequency map using a hash table that stores how many times each card appears. Iterate through the sorted array. When you encounter a card that still has remaining count, try to build a consecutive sequence starting from that value: x, x+1, x+2 ... x+groupSize-1. For each number in this range, check the frequency map and decrement counts as cards are used. If any required card is missing, forming valid groups becomes impossible.
The greedy insight is simple: always start sequences from the smallest available card. If you skip it and try to start later, the smaller card could never fit into a valid consecutive group. Sorting guarantees that groups are built in the correct order, while the frequency map ensures constant-time lookups. This method combines sorting with a greedy strategy and works well in interviews because it is easy to reason about and implement.
Approach 2: Using Multiset / Sorted List (O(n log n) time, O(n) space)
A more structured alternative uses a multiset or ordered map (such as multiset in C++ or a balanced tree structure). Insert all cards into the ordered structure so the smallest value can always be retrieved efficiently. Repeatedly take the smallest card and attempt to build a consecutive sequence of length groupSize. For each next value in the sequence, check if it exists in the multiset. If it does, remove one instance; if it doesn't, the grouping fails.
The ordered structure automatically keeps elements sorted, eliminating the need for a separate sort step but still giving O(log n) insertion and deletion. This makes the overall complexity O(n log n). This approach is common in C++ implementations where multiset operations are convenient and expressive.
Recommended for interviews: The sorting + greedy approach is usually the expected answer. It demonstrates clear reasoning about ordering constraints and efficient use of a frequency map. The multiset approach is also valid but slightly heavier due to tree operations. Showing the greedy reasoning—starting from the smallest unused card and forming consecutive sequences—signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Greedy with Frequency Map | O(n log n) | O(n) | Best general solution; easy to reason about and common in interviews |
| Multiset / Sorted List | O(n log n) | O(n) | Useful in languages with built-in ordered sets like C++ multiset |