Hand of Straights

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.

In other words, you need to check if all cards can be divided into groups where:

Each group has exactly groupSize cards
The card values in each group form a consecutive increasing sequence (e.g., [3, 4, 5])
Every card is used exactly once

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]. Each group has 3 cards with consecutive values, and all 9 cards are used exactly once.

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4

Output: false

Explanation: Alice has 5 cards but needs groups of size 4. Since 5 % 4 ≠ 0, it's impossible to divide 5 cards evenly into groups of 4. The closest attempt [1,2,3,4] leaves card 5 without a complete group.

Constraints

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

Editorial

Brute Force

Intuition

The most natural approach is: sort the cards, then greedily form groups starting from the smallest available card.

Think about it — if you have a card with value x and it's the smallest card remaining, there's no group that can use x in the middle or end (since all smaller cards are gone). So x must start a new group. From there, you need x+1, x+2, ..., x+groupSize-1 to complete that group.

The algorithm:

First check: if the total number of cards isn't divisible by groupSize, return false immediately.
Count the frequency of each card value using a hash map.
Sort the hand.
Walk through the sorted hand. For each card with a remaining count > 0, treat it as the start of a new group and try to form groupSize consecutive cards.
If any required consecutive card is missing (count = 0), return false.
If all groups form successfully, return true.

Step-by-Step

Let's trace through hand = [1,2,3,6,2,3,4,7,8], groupSize = 3:

Setup: Sort → [1,2,2,3,3,4,6,7,8]. Count: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}.

Check: 9 cards ÷ 3 = 3 groups. 9 % 3 = 0 ✓

Card 1: count[1]=1 > 0 → Start group at 1. Need [1,2,3].

count[1]: 1→0 ✓
count[2]: 2→1 ✓
count[3]: 2→1 ✓
Group [1,2,3] formed!

Card 2: count[2]=1 > 0 → Start group at 2. Need [2,3,4].

count[2]: 1→0 ✓
count[3]: 1→0 ✓
count[4]: 1→0 ✓
Group [2,3,4] formed!

Card 2 (again): count[2]=0 → Skip (already used).

Card 3, 3, 4: All have count=0 → Skip.

Card 6: count[6]=1 > 0 → Start group at 6. Need [6,7,8].

count[6]: 1→0 ✓
count[7]: 1→0 ✓
count[8]: 1→0 ✓
Group [6,7,8] formed!

Cards 7, 8: count=0 → Skip.

Result: All cards grouped successfully → true.

Code

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

        unordered_map<int,int> count;
        for (int card : hand)
            count[card]++;

        sort(hand.begin(), hand.end());

        for (int num : hand) {
            if (count[num] > 0) {
                for (int i = num;
                     i < num + groupSize; i++) {
                    if (count[i] == 0)
                        return false;
                    count[i]--;
                }
            }
        }
        return true;
    }
};

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

        count = Counter(hand)
        hand.sort()

        for num in hand:
            if count[num]:
                for i in range(num, num + groupSize):
                    if not count[i]:
                        return False
                    count[i] -= 1
        return True

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

        Map<Integer,Integer> count = new HashMap<>();
        for (int card : hand)
            count.merge(card, 1, Integer::sum);

        Arrays.sort(hand);

        for (int num : hand) {
            if (count.get(num) > 0) {
                for (int i = num;
                     i < num + groupSize; i++) {
                    if (count.getOrDefault(i, 0) == 0)
                        return false;
                    count.merge(i, -1, Integer::sum);
                }
            }
        }
        return true;
    }
}

Complexity

Time Complexity: O(N log N + N × W) where N is the number of cards and W is groupSize. Sorting costs O(N log N). We iterate through all N sorted cards, and for each group start, the inner loop runs W times. Since there are N/W group starts, the total inner work is N/W × W = N. Overall: O(N log N).

Space Complexity: O(N) for the frequency map storing at most N distinct card values.

Why This Approach Is Not Efficient

The sorting approach works but has a key inefficiency: we iterate over the entire sorted array, including cards that have already been used (count = 0). In a worst case like [1,1,1,...,1,2,2,2,...,2,3,3,3,...,3] with thousands of duplicates, we repeatedly skip over already-consumed cards, wasting iterations.

Additionally, sorting the entire array is wasteful when we only care about the smallest available card at each step — we don't need all cards in order, just the current minimum.

Key insight: A min-heap of unique card values gives us the smallest available card in O(log M) time (where M is the number of distinct values), without sorting the entire array including duplicates. When a card value's count drops to 0, we remove it from the heap. This ensures we never waste time on fully-consumed values.

Better Approach - Min-Heap with Frequency Map

Intuition

Instead of sorting the entire hand (including duplicates), we use a min-heap containing only the unique card values and a frequency map tracking how many of each card remain.

The heap always tells us the smallest available card value. We peek at the top of the heap (the minimum), and attempt to form a group starting from that value.

A critical validation: when a card's count reaches 0 during group formation, it must be the current minimum in the heap. Why? If value x has count 0 but x is NOT the heap minimum, it means some smaller value y < x still exists. But we're in the middle of forming a group that includes x, and y hasn't been used yet — y can never be part of a valid consecutive group starting before x because we've already consumed the cards between the group start and x. This gap means grouping is impossible.

This check catches invalid groupings early, such as [1,2,3,3,4,5,6,7] with groupSize = 4 — forming group [1,2,3,4] leaves count[3]=1, count[5]=1, count[6]=1, count[7]=1. Trying to form a group from min=3 needs [3,4,5,6], but count[4]=0 and 4 ≠ heap min (which is 3). Failure detected!

Step-by-Step

Let's trace through hand = [1,2,3,6,2,3,4,7,8], groupSize = 3:

Setup: Count: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}. Heap of unique values: [1,2,3,4,6,7,8].

Group 1: Heap top = 1. Form group starting at 1: need [1,2,3].

count[1]: 1→0. count[1]=0 and heap[0]=1? Yes → pop 1 from heap.
count[2]: 2→1. count[2]>0 → keep.
count[3]: 2→1. count[3]>0 → keep.
Group [1,2,3] formed! Heap: [2,3,4,6,7,8].

Group 2: Heap top = 2. Form group starting at 2: need [2,3,4].

count[2]: 1→0. count[2]=0 and heap[0]=2? Yes → pop 2.
count[3]: 1→0. count[3]=0 and heap[0]=3? Yes → pop 3.
count[4]: 1→0. count[4]=0 and heap[0]=4? Yes → pop 4.
Group [2,3,4] formed! Heap: [6,7,8].

Group 3: Heap top = 6. Form group starting at 6: need [6,7,8].

count[6]: 1→0 → pop 6.
count[7]: 1→0 → pop 7.
count[8]: 1→0 → pop 8.
Group [6,7,8] formed! Heap: [].

Heap empty → return true.

Build frequency map and min-heap of unique card values — Build frequency map and min-heap of unique card values.

Code

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

        unordered_map<int,int> count;
        for (int card : hand)
            count[card]++;

        priority_queue<int, vector<int>,
                       greater<int>> minH;
        for (auto& [val, _] : count)
            minH.push(val);

        while (!minH.empty()) {
            int first = minH.top();
            for (int i = first;
                 i < first + groupSize; i++) {
                if (count.find(i) == count.end()
                    || count[i] == 0)
                    return false;
                count[i]--;
                if (count[i] == 0) {
                    if (i != minH.top())
                        return false;
                    minH.pop();
                }
            }
        }
        return true;
    }
};

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

        count = Counter(hand)
        minH = list(count.keys())
        heapq.heapify(minH)

        while minH:
            first = minH[0]
            for i in range(first, first + groupSize):
                if i not in count or count[i] == 0:
                    return False
                count[i] -= 1
                if count[i] == 0:
                    if i != minH[0]:
                        return False
                    heapq.heappop(minH)
        return True

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

        Map<Integer,Integer> count = new HashMap<>();
        for (int card : hand)
            count.merge(card, 1, Integer::sum);

        PriorityQueue<Integer> minH =
            new PriorityQueue<>(count.keySet());

        while (!minH.isEmpty()) {
            int first = minH.peek();
            for (int i = first;
                 i < first + groupSize; i++) {
                if (!count.containsKey(i)
                    || count.get(i) == 0)
                    return false;
                count.merge(i, -1, Integer::sum);
                if (count.get(i) == 0) {
                    if (i != minH.peek())
                        return false;
                    minH.poll();
                }
            }
        }
        return true;
    }
}

Complexity

Time Complexity: O(N + M × W × log M) where N is the total number of cards, M is the number of distinct card values, and W is groupSize. Building the count map takes O(N). Heapifying M unique values costs O(M). We form N/W groups, each requiring W steps with potential O(log M) heap pops. Total: O(N + M × W × log M). In the worst case (all unique), M = N and this is O(N log N).

Space Complexity: O(M) for the frequency map and the min-heap, where M is the number of distinct values. In the worst case, M = N.

Why This Approach Is Not Efficient

The min-heap approach is clean and correct, but it has structural overhead:

Inner loop per group: For each group, the inner loop runs groupSize times, performing hash map lookups and potential heap operations. With many groups, this repeated work adds up.
Heap maintenance: Each heap pop costs O(log M). In the worst case, we pop all M values, costing O(M log M) total.
Per-group processing: The algorithm forms one group at a time. If two groups share the same starting range (e.g., both start at 2), it processes them sequentially with separate heap iterations.

Key insight for improvement: Instead of forming groups one at a time, we can process all cards in a single sweep over the sorted unique values. Track how many groups are currently "open" (waiting for the next consecutive card). When processing value v, some of those count[v] cards extend existing open groups, and the rest start new groups. A queue tracks when groups close (after reaching groupSize length). This eliminates the inner loop and all heap operations — just one pass over sorted unique values.

Optimal Approach - Open Group Tracking

Intuition

Instead of forming groups one at a time, we process all card values in sorted order and track how many groups are currently "open" — i.e., groups that have been started but haven't yet reached groupSize length.

At each card value num, we know:

open_groups groups are waiting for num as their next card
count[num] is how many cards of value num we have

Validation rules:

If there are open groups but num isn't consecutive to the previous value (gap detected), return false — those open groups can never be completed.
If open_groups > count[num], return false — not enough cards to satisfy all waiting groups.

If validation passes:

open_groups cards of value num extend existing groups
The remaining count[num] - open_groups cards start new groups
Push this count of new groups onto a queue
When the queue reaches size groupSize, the oldest batch of groups has been extended groupSize times → they're complete! Pop the front and reduce open_groups.

After processing all values, open_groups must be 0 (all groups complete).

Step-by-Step

Let's trace through hand = [1,2,3,6,2,3,4,7,8], groupSize = 3:

Setup: Count: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}. Sorted unique: [1,2,3,4,6,7,8].
open_groups = 0, last_num = -1, queue = [].

Process num=1: No open groups → no gap/count check needed.

new_groups = count[1] - open_groups = 1 - 0 = 1. Push 1 to queue.
open_groups = count[1] = 1. last_num = 1. Queue: [1] (size 1 < 3).

Process num=2: open_groups=1 > 0, num=2 = last+1 ✓ (consecutive). count[2]=2 ≥ 1 ✓.

new_groups = 2 - 1 = 1. Push 1 to queue.
open_groups = 2. last_num = 2. Queue: [1, 1] (size 2 < 3).

Process num=3: open_groups=2, num=3 = last+1 ✓. count[3]=2 ≥ 2 ✓.

new_groups = 2 - 2 = 0. Push 0 to queue.
open_groups = 2. Queue: [1, 1, 0] (size 3 = groupSize!).
Pop front: popped = 1. open_groups = 2 - 1 = 1.
This means 1 group that started at value 1 is now complete: [1,2,3] ✓

Process num=4: open_groups=1, num=4 = last+1 ✓. count[4]=1 ≥ 1 ✓.

new_groups = 1 - 1 = 0. Push 0.
open_groups = 1. Queue: [1, 0, 0] (size 3).
Pop front: popped = 1. open_groups = 1 - 1 = 0.
1 group that started at value 2 is now complete: [2,3,4] ✓

Process num=6: open_groups=0, num=6 ≠ last+1=5 but open_groups=0 → OK (no groups left waiting).

new_groups = 1 - 0 = 1. Push 1.
open_groups = 1. Queue: [0, 1] (reset, size 2 < 3).

Process num=7: open_groups=1, num=7 = last+1 ✓. count[7]=1 ≥ 1 ✓.

new_groups = 1 - 1 = 0. Push 0.
open_groups = 1. Queue: [0, 1, 0] (size 3).
Pop front: popped = 0. open_groups = 1 - 0 = 1.

Process num=8: open_groups=1, num=8 = last+1 ✓. count[8]=1 ≥ 1 ✓.

new_groups = 1 - 1 = 0. Push 0.
open_groups = 1. Queue: [1, 0, 0] (size 3).
Pop front: popped = 1. open_groups = 1 - 1 = 0.
Group [6,7,8] complete ✓

Done: open_groups = 0 → return true.

Build frequency map and sort unique values — Build frequency map and sort unique values. Initialize open_groups=0, queue=[].

Code

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

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

        deque<int> q;
        int lastNum = -1, openGroups = 0;

        for (auto& [num, cnt] : count) {
            if ((openGroups > 0 &&
                 num > lastNum + 1) ||
                openGroups > cnt)
                return false;

            q.push_back(cnt - openGroups);
            lastNum = num;
            openGroups = cnt;

            if ((int)q.size() == groupSize) {
                openGroups -= q.front();
                q.pop_front();
            }
        }
        return openGroups == 0;
    }
};

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

        count = Counter(hand)
        q = deque()
        last_num, open_groups = -1, 0

        for num in sorted(count):
            if ((open_groups > 0
                 and num > last_num + 1)
                or open_groups > count[num]):
                return False

            q.append(count[num] - open_groups)
            last_num = num
            open_groups = count[num]

            if len(q) == groupSize:
                open_groups -= q.popleft()

        return open_groups == 0

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

        TreeMap<Integer,Integer> count =
            new TreeMap<>();
        for (int card : hand)
            count.merge(card, 1, Integer::sum);

        Deque<Integer> q = new ArrayDeque<>();
        int lastNum = -1, openGroups = 0;

        for (var entry : count.entrySet()) {
            int num = entry.getKey();
            int cnt = entry.getValue();

            if ((openGroups > 0 &&
                 num > lastNum + 1) ||
                openGroups > cnt)
                return false;

            q.addLast(cnt - openGroups);
            lastNum = num;
            openGroups = cnt;

            if (q.size() == groupSize) {
                openGroups -= q.pollFirst();
            }
        }
        return openGroups == 0;
    }
}

Complexity

Time Complexity: O(N + M log M) where N is the total number of cards and M is the number of distinct card values. Building the frequency map costs O(N). Sorting the unique keys costs O(M log M). The single pass over M unique values does O(1) work per value (one comparison, one queue push, one conditional pop). Total: O(N + M log M). When there are many duplicates (M << N), this is significantly faster than sorting all N cards.

Space Complexity: O(M) for the frequency map (or TreeMap) and the deque, which holds at most groupSize entries. In the worst case (all cards unique), M = N.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Hand of Straights

Description

Examples

Constraints

Editorial

Brute Force

Intuition

Step-by-Step

Code

Complexity

Why This Approach Is Not Efficient

Better Approach - Min-Heap with Frequency Map

Intuition

Step-by-Step

Code

Complexity

Why This Approach Is Not Efficient

Optimal Approach - Open Group Tracking

Intuition

Step-by-Step

Code

Complexity