LeetCode 846 - Hand of Straights

LeetCode Problem 846

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine whether a given collection of cards can be rearranged into groups of consecutive numbers, each of size groupSize. Each card is represented by an integer in the array hand, and Alice wants to form groups such that within each group, the card numbers are consecutive and the total number of cards in each group equals groupSize. The function should return true if such a rearrangement is possible, and false otherwise.

The constraints tell us several key points. The length of hand can go up to 10,000, which makes an $O(n^2)$ approach potentially too slow. Card values can be as large as $10^9$, so we cannot rely on array indices to represent values directly and need a data structure like a hash map to count occurrences. Finally, groupSize can be as small as 1 or equal to the length of the hand, which means we need to handle both minimal and maximal group scenarios.

Important edge cases include: groupSize not dividing the total number of cards, multiple duplicates of the same card value, and unsorted input. A naive implementation that simply looks for consecutive sequences without counting duplicates would fail in these scenarios.

Approaches

A brute-force approach would repeatedly try to form groups by picking the smallest remaining card and checking for consecutive cards until either all cards are used or a group cannot be formed. This works logically because it enforces the consecutive condition, but it is inefficient. Every time we scan the remaining cards to check for consecutive values, the complexity can become $O(n^2)$, which is too slow for the maximum input size.

The key insight for an optimal solution is that counting card occurrences and always starting from the smallest card ensures we never "lock out" a card that could be part of a valid sequence. Using a hash map to track frequencies and iterating over the cards in sorted order allows us to greedily form sequences efficiently. By reducing the count of each card in the consecutive sequence, we ensure that the same card is not reused improperly, and any leftover count signals an impossible grouping.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Repeatedly searches for consecutive sequences by scanning remaining cards
Optimal	O(n log n)	O(n)	Uses a frequency map and sorts unique cards to greedily form sequences

Algorithm Walkthrough

1. Count the occurrences of each card in hand using a hash map or dictionary. This allows quick access to how many times a card is available.

2. Sort the unique card values. Sorting ensures we always start forming sequences from the smallest available card, which is necessary to maintain consecutiveness.

3. Iterate over the sorted unique card values. For each card:

4. Check its frequency in the map. If the frequency is zero, it has already been fully used in previous sequences, so skip it.

5. Otherwise, attempt to form a sequence of length groupSize starting from this card.

6. For each card current in the sequence, check that it exists in the map with at least the required frequency. If any card is missing, return false.

7. Reduce the count of each card in the sequence by the count of the starting card. This ensures that duplicates are correctly accounted for.

8. If all cards are successfully used in sequences, return true.

Why it works: The algorithm maintains the invariant that we always use the smallest available card to form sequences, preventing "holes" in the consecutive sequences. Reducing the frequency count ensures no card is reused incorrectly. Sorting guarantees that we process sequences in increasing order, so no consecutive requirement is violated.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        
        count = Counter(hand)
        for card in sorted(count):
            if count[card] > 0:
                freq = count[card]
                for i in range(card, card + groupSize):
                    if count[i] < freq:
                        return False
                    count[i] -= freq
        return True

The implementation first checks if the hand length is divisible by groupSize. If not, forming groups is impossible. Using Counter, we track card counts. Sorting the keys ensures we always start from the smallest available card. For each card with a positive count, we attempt to form a sequence of groupSize, reducing counts appropriately. If a required card is missing or insufficient, the function immediately returns false. If all sequences succeed, the function returns true.

Go Solution

import "sort"

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 {
        return false
    }

    count := make(map[int]int)
    for _, card := range hand {
        count[card]++
    }

    unique := make([]int, 0, len(count))
    for card := range count {
        unique = append(unique, card)
    }
    sort.Ints(unique)

    for _, card := range unique {
        freq := count[card]
        if freq > 0 {
            for i := 0; i < groupSize; i++ {
                nextCard := card + i
                if count[nextCard] < freq {
                    return false
                }
                count[nextCard] -= freq
            }
        }
    }
    return true
}

In Go, we use a map to count card frequencies and a slice to store sorted unique card values. The algorithm is nearly identical to Python. Go-specific considerations include explicitly creating a slice for unique keys and using sort.Ints for sorting. Map access is safe and returns zero for missing keys, matching the Python Counter behavior.

Worked Examples

Example 1: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Step	Card	freq	Sequence attempted	Count after sequence
1	1	1	1,2,3	{1:0,2:1,3:1,4:1,6:1,7:1,8:1}
2	2	1	2,3,4	{2:0,3:0,4:0,6:1,7:1,8:1}
3	6	1	6,7,8	{6:0,7:0,8:0}

All counts reduced to zero. Return true.

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

Step	Card	freq	Sequence attempted	Count after sequence
1	1	1	1,2,3,4	{1:0,2:0,3:0,4:0,5:1}

Next card is 5, but cannot form a sequence of 4. Return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting unique cards dominates, counting and sequence forming is O(n)
Space	O(n)	Counter/map stores frequency of each card

The dominant cost is sorting the unique cards, which is at most O(n log n). The counting operations over the entire hand take linear time, and the map requires O(n) space.

Test Cases

# Provided examples
assert Solution().isNStraightHand([1,2,3,6,2,3,4,7,8], 3) == True  # normal case
assert Solution().isNStraightHand([1,2,3,4,5], 4) == False        # cannot form groups

# Edge cases
assert Solution().isNStraightHand([], 1) == True                    # empty hand
assert Solution().isNStraightHand([1], 1) == True                   # single card
assert Solution().isNStraightHand([1,1,2,2,3,3], 3) == True        # duplicates with proper grouping
assert Solution().isNStraightHand([1,2,3,4], 5) == False           # groupSize > len(hand)
assert Solution().isNStraightHand([1,2,3,4,5,6], 2) == True        # multiple pairs
assert Solution().isNStraightHand([5,1,2,6,3,4], 3) == True        # unsorted input

Test	Why
[1,2,3,6,2,3,4,7,8], 3	Valid consecutive groups with duplicates
[1,2,3,4,5], 4	Hand length not divisible by groupSize
[]	Empty hand edge case
[1], 1	Single card forms one valid group
[1,1,2,2,3,3], 3	Duplicates can form multiple valid sequences
[1,2,3,4], 5	groupSize greater than hand length
[1,2