Hand of Straights

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazon

Problem Description

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

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

Constraints

1 ≤ hand.length ≤ 10000
0 ≤ hand[i] ≤ 10⁹
1 ≤ groupSize ≤ hand.length

Frequency Map and Greedy Minimum Starting

If the total number of cards is not divisible by groupSize, we can immediately return false.

To rearrange into consecutive groups, we must start a group using the smallest card available in our hand.

Build a sorted frequency map (e.g. TreeMap in Java, sorted keys list/heap in Python, std::map in C++) of the card values.
While cards remain, find the smallest available card first.
Try to form a consecutive group of length groupSize starting from first:
- For each value val from first to first + groupSize - 1:
  - If val is not available in our frequency map, return false.
  - Decrement the count of val in the map. If the count reaches 0, remove it.

If we successfully exhaust all cards, return true.

Solution: Sorted Map Greedy

import java.util.*;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;

        TreeMap<Integer, Integer> counts = new TreeMap<>();
        for (int card : hand) {
            counts.put(card, counts.getOrDefault(card, 0) + 1);
        }

        while (!counts.isEmpty()) {
            int first = counts.firstKey();
            for (int i = 0; i < groupSize; i++) {
                int nextCard = first + i;
                if (!counts.containsKey(nextCard)) {
                    return false;
                }
                int count = counts.get(nextCard);
                if (count == 1) {
                    counts.remove(nextCard);
                } else {
                    counts.put(nextCard, count - 1);
                }
            }
        }

        return true;
    }
}

from collections import Counter
import heapq

class Solution:
    def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False

        counts = Counter(hand)
        min_heap = list(counts.keys())
        heapq.heapify(min_heap)

        while min_heap:
            first = min_heap[0]
            
            # try to form a straight starting from 'first'
            for i in range(groupSize):
                next_card = first + i
                if counts[next_card] == 0:
                    return False
                counts[next_card] -= 1
                
            # clean up heap top elements that have frequency 0
            while min_heap and counts[min_heap[0]] == 0:
                heapq.heappop(min_heap)

        return True

#include <vector>
#include <map>

class Solution {
public:
    bool isNStraightHand(std::vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false;

        std::map<int, int> counts;
        for (int card : hand) counts[card]++;

        while (!counts.empty()) {
            int first = counts.begin()->first;
            for (int i = 0; i < groupSize; i++) {
                int nextCard = first + i;
                if (counts[nextCard] == 0) {
                    return false;
                }
                if (--counts[nextCard] == 0) {
                    counts.erase(nextCard);
                }
            }
        }

        return true;
    }
};

Complexity Analysis:

Time Complexity: O(N log K) where N is the number of cards in hand and K is the number of distinct cards. Inserting and lookup/removal operations on sorted map/heap take logarithmic time.
Space Complexity: O(K) to store the distinct cards in the frequency map.