Hand of Straights

LeetCode 846: Hand of Straights Solution & Explanation

Problem Overview

TL;DR: Sort the distinct card values, count their frequencies, and greedily start the required number of consecutive groups at the smallest remaining value.

The LeetCode 846 Solution must determine whether every card can be partitioned into groups of exactly groupSize consecutive values. Duplicate card values represent separate cards and can be distributed across different groups.

For LeetCode 846: Hand of Straights, every card must be used exactly once. A partition is valid only if each group contains values such as [x, x + 1, x + 2] with no missing integer.

A necessary condition is:

hand.length % groupSize == 0

If the number of cards is not divisible by the required group size, a valid partition is impossible.

Brute Force Approach for Hand of Straights

A direct approach is to repeatedly construct one group at a time:

1. Find the smallest unused card.
2. Search for the next groupSize - 1 consecutive values.
3. Remove those cards from the hand.
4. Repeat until all cards are used.

A naive implementation may scan the remaining cards for every required value and physically remove cards from an array or list.

Naive Pseudocode

if number of cards is not divisible by groupSize:
    return false

while unused cards remain:
    start = smallest unused card

    for offset from 0 to groupSize - 1:
        required = start + offset

        find one unused card equal to required
        if it does not exist:
            return false

        remove that card

return true

Complexity

If searching for and removing each card requires scanning the remaining collection, the worst-case time complexity can reach:

O(n^2)

where n = hand.length.

With n up to 10^4, repeated linear searches and removals can perform tens of millions of operations. Depending on the implementation and language, this can result in Time Limit Exceeded. The brute force method also does not efficiently aggregate duplicate values, even though duplicates are central to this problem.

Algorithm Strategy: Greedy Patterns

1. Verify that the total number of cards is divisible by groupSize.
2. Build a frequency map from card value to remaining count.
3. Store the frequencies in sorted-key order.
4. Visit each distinct value from smallest to largest.
5. Let groups be the remaining count of the current value.
6. If groups is zero, continue.
7. For every offset from 0 through groupSize - 1:
   • Require the value current value + offset.
   • Verify that its remaining count is at least groups.
   • Subtract groups from that count.
8. If every required interval can be consumed, return true.

The sorted map or sorted keys enforce the boundary condition that no smaller remaining value is skipped.

Execution Flow

For example, consider:

hand = [20, 21, 22, 23, 21, 22, 23, 24]
groupSize = 4

The frequency map is:

20: 1
21: 2
22: 2
23: 2
24: 1

The algorithm proceeds as follows:

1. The total number of cards is divisible by 4.
2. The smallest value is 20, with frequency 1.
3. One group must begin at 20, so consume one card from:
   textCopy

   20, 21, 22, 23

4. Remaining frequencies become:
   textCopy

   20: 0
   21: 1
   22: 1
   23: 1
   24: 1

5. The value 20 now has frequency zero, so no new group starts there.
6. The next remaining value is 21, with frequency 1.
7. Consume one card from:
   textCopy

   21, 22, 23, 24

8. All frequencies become zero.
9. Since every card was consumed successfully, return true.

If a required value is missing, the algorithm returns false immediately. For example, if the smallest remaining value is 14 and 16 is unavailable, a group beginning at 14 cannot be completed.

Proof of Correctness

We prove that the algorithm returns true exactly when a valid partition exists.

Lemma 1: Every remaining copy of the smallest value must start a group

Let x be the smallest value with a positive remaining frequency.

No unused card has a value smaller than x. Therefore, a group containing a remaining card valued x cannot have an earlier consecutive value. Since each group must contain consecutive values, every remaining copy of x must be the first card of a group.

Thus, if count[x] = k, exactly k groups must start at x.

Lemma 2: Consuming k copies from every required value is necessary

Each group that starts at x requires one card of every value from x through x + groupSize - 1.

Because there are k groups starting at x, each required value must have at least k remaining copies. Subtracting k from each frequency is therefore necessary in every valid partition.

If any required frequency is less than k, no valid partition can contain all k groups, so returning false is correct.

Lemma 3: The greedy consumption preserves feasibility

The algorithm consumes exactly the cards that every valid partition must use for groups beginning at the smallest remaining value. It does not make an arbitrary choice among possible starts; the starts are forced by the smallest unresolved value.

After this consumption, the remaining cards must form the remaining groups independently. Therefore, if a valid partition exists before the step, the residual frequencies remain feasible after the step.

Theorem

If the algorithm returns false, some required consecutive value lacks enough remaining copies, so no valid partition exists by Lemma 2.

If the algorithm returns true, every required group was formed successfully and all frequencies were reduced to zero. Therefore, every card belongs to exactly one valid group.

Hence, the algorithm returns true if and only if the hand can be partitioned into valid consecutive groups.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 406: Queue Reconstruction by Height
• LeetCode 1029: Two City Scheduling
• LeetCode 455: Assign Cookies
• LeetCode 135: Candy

These problems use greedy decisions that become reliable after organizing the input by a relevant order. Sorting exposes the next constrained item, allowing each local choice to preserve feasibility for the remaining items. In Hand of Straights, that order is the ascending card value, and the local decision consumes all groups forced by the smallest remaining frequency.

Reference Implementation

C++ Solution for LeetCode 846

1class Solution {
2public:
3    bool isNStraightHand(vector<int>& hand, int groupSize) {
4        if (hand.size() % groupSize != 0) {
5            return false;
6        }
7
8        map<long long, int> count;
9        for (int card : hand) {
10            ++count[card];
11        }
12
13        for (auto it = count.begin(); it != count.end(); ++it) {
14            int groups = it->second;
15            if (groups == 0) {
16                continue;
17            }
18
19            long long start = it->first;
20            for (int offset = 0; offset < groupSize; ++offset) {
21                auto next = count.find(start + offset);
22                if (next == count.end() || next->second < groups) {
23                    return false;
24                }
25                next->second -= groups;
26            }
27        }
28
29        return true;
30    }
31};

The map keeps card values sorted. For each value with a positive remaining count, the implementation consumes that many groups across the required consecutive interval. long long protects the arithmetic when calculating start + offset.

Java Solution for LeetCode 846

1class Solution {
2    public boolean isNStraightHand(int[] hand, int groupSize) {
3        if (hand.length % groupSize != 0) {
4            return false;
5        }
6
7        java.util.TreeMap<Integer, Integer> counts = new java.util.TreeMap<>();
8        for (int value : hand) {
9            counts.put(value, counts.getOrDefault(value, 0) + 1);
10        }
11
12        for (int value : counts.keySet()) {
13            int groups = counts.get(value);
14            if (groups == 0) {
15                continue;
16            }
17
18            long end = (long) value + groupSize;
19            for (long card = value; card < end; card++) {
20                int current = 0;
21                if (card >= Integer.MIN_VALUE && card <= Integer.MAX_VALUE) {
22                    current = counts.getOrDefault((int) card, 0);
23                }
24
25                if (current < groups) {
26                    return false;
27                }
28
29                int cardValue = (int) card;
30                counts.put(cardValue, current - groups);
31            }
32        }
33
34        return true;
35    }
36}

TreeMap provides sorted keys, so iteration follows the required greedy order. The loop uses long for the interval boundary to avoid integer overflow when calculating the end of a consecutive group.

Python Solution for LeetCode 846

1from typing import List, Optional
2from collections import Counter
3
4
5class Solution:
6    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
7        if len(hand) % groupSize != 0:
8            return False
9
10        counts = Counter(hand)
11
12        for value in sorted(counts):
13            groups = counts[value]
14            if groups == 0:
15                continue
16
17            for card in range(value, value + groupSize):
18                if counts.get(card, 0) < groups:
19                    return False
20                counts[card] -= groups
21
22        return True

Counter stores frequencies, while sorted(counts) processes distinct values from smallest to largest. The implementation directly applies the greedy invariant by subtracting the current frequency from every required consecutive value.