846. Hand of Straights (Medium)

Problem

Given an array hand of integers (each a card value) and an integer groupSize, return true if the cards can be rearranged into groups each of which is a run of groupSize consecutive values.

Example

hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 → true ([1,2,3], [2,3,4], [6,7,8])
hand = [1,2,3,4,5], groupSize = 4 → false

LeetCode 846 · Link · Medium

Approach 1: Brute force, try every partitioning

Exponential. Skip.

Approach 2: Sort + per-smallest consumption (canonical greedy)

Count occurrences. Repeatedly take the smallest remaining value x; it must start a run of x, x+1, ..., x + groupSize - 1, remove one of each. If at any point you can’t, return false.

from collections import Counter

def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:             # L1: O(1) quick reject
        return False
    counts = Counter(hand)                      # L2: O(n)
    for x in sorted(counts):                    # L3: O(u log u) where u = distinct values
        c = counts[x]                           # L4: O(1)
        if c == 0:
            continue
        for k in range(group_size):             # L5: O(group_size) per distinct value
            if counts[x + k] < c:              # L6: O(1)
                return False
            counts[x + k] -= c                 # L7: O(1)
    return True

Where the time goes, line by line

Variables: n = len(hand), u = number of distinct card values, k = group_size.

Line	Per-call cost	Times executed	Contribution
L2 (Counter)	O(1)	n	O(n)
L3 (sorted iteration)	O(u log u)	1	O(n log n) ← dominates
L5-L7 (group consumption)	O(group_size)	u times	O(n · k)

Sorting the distinct values is O(u log u) where u ≤ n, so O(n log n). The inner consumption loop does O(group_size) work per distinct value; total work across all distinct values is bounded by O(n · group_size).

Complexity

Time: O(n log n + n · k), driven by L3 (sort) and L5/L6/L7 (group consumption).
Space: O(n) for the Counter.

Approach 3: Min-heap + lazy consumption

Min-heap of remaining values; pop smallest; consume one of each of the next k values.

import heapq
from collections import Counter

def is_n_straight_hand_heap(hand, group_size):
    if len(hand) % group_size != 0:             # L1: O(1)
        return False
    counts = Counter(hand)                      # L2: O(n)
    heap = list(counts)                         # L3: O(u)
    heapq.heapify(heap)                         # L4: O(u) Floyd's
    while heap:                                 # L5: outer loop
        x = heap[0]                             # L6: O(1) peek min
        if counts[x] == 0:
            heapq.heappop(heap)                 # L7: O(log u) pop exhausted
            continue
        for k in range(group_size):             # L8: O(group_size) per group start
            if counts[x + k] == 0:
                return False
            counts[x + k] -= 1                 # L9: O(1)
        while heap and counts[heap[0]] == 0:
            heapq.heappop(heap)                 # L10: O(log u) cleanup
    return True

Where the time goes, line by line

Variables: n = len(hand), u = number of distinct card values, k = group_size.

Line	Per-call cost	Times executed	Contribution
L2 (Counter)	O(1)	n	O(n)
L4 (heapify)	O(u)	1	O(n)
L7, L10 (heap pops)	O(log u)	up to u	O(n log n) ← dominates
L8-L9 (consumption)	O(group_size)	n/group_size groups	O(n · k)

Heap pops cost O(log u) and happen at most u times; consumption loops cost O(group_size) per group, totaling O(n · group_size / group_size) = O(n) consumption steps.

Complexity

Time: O(n log n + n · k), same as Approach 2.
Space: O(n) for Counter and heap.

Summary

Approach	Time	Space
Enumerate partitions	exponential	O(n)
Sort + per-smallest	O(n log n + n · k)	O(n)
Min-heap + lazy	O(n log n + n · k)	O(n)

The greedy choice, always start the next group from the smallest remaining value, is forced: if the smallest value can’t start a group, no group can contain it, so the answer is false.

Test cases

# Quick smoke tests, paste into a REPL or save as test_846.py and run.
# Uses the canonical implementation (Approach 2: sort + per-smallest).

from collections import Counter

def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:
        return False
    counts = Counter(hand)
    for x in sorted(counts):
        c = counts[x]
        if c == 0:
            continue
        for k in range(group_size):
            if counts[x + k] < c:
                return False
            counts[x + k] -= c
    return True

def _run_tests():
    assert is_n_straight_hand([1,2,3,6,2,3,4,7,8], 3) == True
    assert is_n_straight_hand([1,2,3,4,5], 4) == False
    assert is_n_straight_hand([1], 1) == True           # single card, group of 1
    assert is_n_straight_hand([1,2,3], 3) == True       # exact one group
    assert is_n_straight_hand([1,2,4], 3) == False      # gap, can't form run
    assert is_n_straight_hand([1,1,2,2,3,3], 3) == True # two complete groups
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Hash Tables, frequency counts (Counter)
Heaps / Priority Queues, smallest-first consumption