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.
We can sort the array first and then use a greedy approach to construct consecutive groups of the given group size:
This Python code first uses a Counter to count occurrences of each card. It then attempts to form groups starting from the smallest card available, reducing counts appropriately.
Time Complexity: O(N log N) due to sorting, where N is the number of cards. Space Complexity: O(N) for storing the counts.
This approach uses a multiset (or similar structure) to represent the occurrence of each card. It uses a similar greedy process as Approach 1 but leverages enhanced data structures for efficient access:
This C++ solution uses a map (similar to a multiset here) to maintain count of each card and iterates with greedy logic to form groups by decreasing the count of cards as it goes.
Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts.
We first check whether the length of the array hand is divisible by groupSize. If it is not, this means that the array cannot be partitioned into multiple subarrays of length groupSize, so we return false.
Next, we use a hash table cnt to count the occurrences of each number in the array hand, and then we sort the array hand.
After that, we iterate over the sorted array hand. For each number x, if cnt[x] neq 0, we enumerate every number y from x to x + groupSize - 1. If cnt[y] = 0, it means that we cannot partition the array into multiple subarrays of length groupSize, so we return false. Otherwise, we decrement cnt[y] by 1.
If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return true.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array hand.
Python
Java
C++
Go
TypeScript
Similar to Solution 1, we first check whether the length of the array hand is divisible by groupSize. If it is not, this means that the array cannot be partitioned into multiple subarrays of length groupSize, so we return false.
Next, we use an ordered set sd to count the occurrences of each number in the array hand.
Then, we repeatedly take the smallest value x from the ordered set and enumerate each number y from x to x + groupSize - 1. If all these numbers appear at least once in the ordered set, we decrement their occurrence count by 1. If any count reaches 0, we remove that number from the ordered set. Otherwise, if we encounter a number that does not exist in the ordered set, it means that the array cannot be partitioned into valid subarrays, so we return false. If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return true.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array hand.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Greedy | Time Complexity: O(N log N) due to sorting, where N is the number of cards. Space Complexity: O(N) for storing the counts. |
| Approach 2: Using Multiset/Sorted List | Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts. |
| Hash Table + Sorting | — |
| Ordered Set | — |
| 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 |
Hand of Straights - Leetcode 846 - Python • NeetCode • 88,819 views views
Watch 9 more video solutions →Practice Hand of Straights with our built-in code editor and test cases.
Practice on FleetCode