Skip to content
AI360Xpert
Back to Greedy
Medium

Hand of Straights

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.

Examples

Input:hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output:true
Alice's hand can be rearranged as [1,2,3], [2,3,4], [6,7,8]
Input:hand = [1,2,3,4,5], groupSize = 4
Output:false
Alice's hand can not be rearranged into groups of 4.

Constraints

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

Greedy with Min-Heap or TreeMap

Approach

First, check if `hand.length % groupSize == 0`. If not, we can't form groups of that size. We can count the occurrences of each card and store them. Since we always want to start a group with the smallest available card, we can process the unique cards in sorted order (using a min-heap or a balanced BST like TreeMap). While our collection is not empty, we pick the minimum card `min`. To form a valid group, we must also have `min+1`, `min+2`, ..., `min+groupSize-1` in our collection. We decrement the count for each of these cards. If any card is missing or its count drops below 0, return false. If its count becomes 0, we remove it from our collection.

Complexity Analysis

Time Complexity
O(n log n)
Space Complexity
O(n)

Time complexity is O(n log n) because we process each element and heap/tree operations take O(log n). Space complexity is O(n) for the frequency map and the heap/tree.

Solution.java
class Solution {    public boolean isNStraightHand(int[] hand, int groupSize) {        if (hand.length % groupSize != 0) {            return false;        }                // TreeMap keeps the keys in sorted order        TreeMap<Integer, Integer> counts = new TreeMap<>();        for (int card : hand) {            counts.put(card, counts.getOrDefault(card, 0) + 1);        }                while (!counts.isEmpty()) {            // Get the smallest card available            int first = counts.firstKey();                        // Try to form a sequence of length groupSize            for (int i = first; i < first + groupSize; i++) {                if (!counts.containsKey(i)) {                    return false;                }                                int count = counts.get(i);                if (count == 1) {                    counts.remove(i);                } else {                    counts.put(i, count - 1);                }            }        }                return true;    }}