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