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

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every partitioning

Recursively pick group_size indices, check they form a consecutive run, then recurse on the rest.

from itertools import combinations

def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:
        return False
    if not hand:
        return True
    n = len(hand)
    for indices in combinations(range(n), group_size):              # L1: C(n, k) groups to try
        group = sorted(hand[i] for i in indices)
        if all(group[i] - group[i - 1] == 1 for i in range(1, len(group))):
            remaining = [hand[i] for i in range(n) if i not in set(indices)]
            if is_n_straight_hand(remaining, group_size):           # L2: recurse on rest
                return True
    return False

function isNStraightHand(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) return false;
    if (hand.length === 0) return true;
    const n = hand.length;
    // Try every combination of groupSize indices
    function* combinations(arr: number[], k: number): Generator<number[]> {
        if (k === 0) { yield []; return; }
        for (let i = 0; i <= arr.length - k; i++) {
            for (const rest of combinations(arr.slice(i + 1), k - 1)) {
                yield [arr[i], ...rest];
            }
        }
    }
    const indices = Array.from({ length: n }, (_, i) => i);
    for (const chosen of combinations(indices, groupSize)) {        // L1: C(n, k) groups
        const group = chosen.map(i => hand[i]).sort((a, b) => a - b);
        if (group.every((v, i) => i === 0 || v - group[i - 1] === 1)) {
            const chosen_set = new Set(chosen);
            const remaining = hand.filter((_, i) => !chosen_set.has(i));
            if (isNStraightHand(remaining, groupSize)) return true; // L2: recurse
        }
    }
    return false;
}

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 { return false }
    if len(hand) == 0 { return true }
    n := len(hand)
    var comb func(start, k int, chosen []int) bool
    comb = func(start, k int, chosen []int) bool {
        if k == 0 {
            group := make([]int, len(chosen))
            copy(group, chosen)
            sort.Ints(group)                                        // L1: C(n, k) groups
            for i := 1; i < len(group); i++ {
                if group[i]-group[i-1] != 1 { return false }
            }
            var rem []int
            used := map[int]bool{}
            for _, idx := range chosen { used[idx] = true }
            for i := 0; i < n; i++ {
                if !used[i] { rem = append(rem, hand[i]) }
            }
            return isNStraightHand(rem, groupSize)                  // L2: recurse on rest
        }
        for i := start; i <= n-k; i++ {
            if comb(i+1, k-1, append(chosen, i)) { return true }
        }
        return false
    }
    return comb(0, groupSize, nil)
}

final class Solution {
    func isNStraightHand(_ hand: [Int], _ groupSize: Int) -> Bool {
        if hand.count % groupSize != 0 { return false }
        func arrange(_ remaining: [Int]) -> Bool {
            if remaining.isEmpty { return true }
            let start = remaining.min()!
            var next = remaining
            for value in start..<(start + groupSize) {
                guard let index = next.firstIndex(of: value) else { return false }
                next.remove(at: index)
            }
            return arrange(next)
        }
        return arrange(hand)
    }
}

Each level tries C(n, k) groups; the recursion has n/k levels. Total combinatorial blow-up. Skip.

Complexity

Time: exponential.
Space: $O(n)$ recursion.

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

function isNStraightHand(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) return false;                // L1: O(1) quick reject
    const counts = new Map<number, number>();
    for (const v of hand) counts.set(v, (counts.get(v) ?? 0) + 1); // L2: O(n)
    const keys = Array.from(counts.keys()).sort((a, b) => a - b);   // L3: O(u log u)
    for (const x of keys) {
        const c = counts.get(x)!;                                   // L4: O(1)
        if (c === 0) continue;
        for (let k = 0; k < groupSize; k++) {                       // L5: O(group_size) per value
            const cur = counts.get(x + k) ?? 0;
            if (cur < c) return false;                              // L6: O(1)
            counts.set(x + k, cur - c);                            // L7: O(1)
        }
    }
    return true;
}

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 { return false }                    // L1: O(1) quick reject
    counts := make(map[int]int)
    for _, v := range hand { counts[v]++ }                          // L2: O(n)
    keys := make([]int, 0, len(counts))
    for k := range counts { keys = append(keys, k) }
    sort.Ints(keys)                                                 // L3: O(u log u)
    for _, x := range keys {
        c := counts[x]                                              // L4: O(1)
        if c == 0 { continue }
        for k := 0; k < groupSize; k++ {                           // L5: O(group_size) per value
            if counts[x+k] < c { return false }                    // L6: O(1)
            counts[x+k] -= c                                       // L7: O(1)
        }
    }
    return true
}

final class Solution {
    func isNStraightHand(_ hand: [Int], _ groupSize: Int) -> Bool {
        if hand.count % groupSize != 0 { return false }
        var counts: [Int: Int] = [:]
        for card in hand { counts[card, default: 0] += 1 }
        for start in counts.keys.sorted() {
            let copies = counts[start, default: 0]
            if copies == 0 { continue }
            for value in start..<(start + groupSize) {
                if counts[value, default: 0] < copies { return false }
                counts[value, default: 0] -= copies
            }
        }
        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.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

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

// Min-heap using a sorted key list (straightforward for interview context)
function isNStraightHandHeap(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) return false;                // L1: O(1)
    const counts = new Map<number, number>();
    for (const v of hand) counts.set(v, (counts.get(v) ?? 0) + 1); // L2: O(n)
    const keys = Array.from(counts.keys()).sort((a, b) => a - b);   // L3: O(u)
    let ki = 0;                                                     // L4: O(u) setup
    while (ki < keys.length) {                                      // L5: outer loop
        const x = keys[ki];
        if ((counts.get(x) ?? 0) === 0) { ki++; continue; }        // L7: skip exhausted
        for (let k = 0; k < groupSize; k++) {                       // L8: O(group_size) per start
            const cur = counts.get(x + k) ?? 0;
            if (cur === 0) return false;
            counts.set(x + k, cur - 1);                            // L9: O(1)
        }
    }
    return true;
}

func isNStraightHandHeap(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 { return false }                    // L1: O(1)
    counts := make(map[int]int)
    for _, v := range hand { counts[v]++ }                          // L2: O(n)
    keys := make([]int, 0, len(counts))
    for k := range counts { keys = append(keys, k) }
    sort.Ints(keys)                                                 // L3: O(u)
    ki := 0
    for ki < len(keys) {                                            // L5: outer loop
        x := keys[ki]
        if counts[x] == 0 { ki++; continue }                       // L7: skip exhausted
        for k := 0; k < groupSize; k++ {                           // L8: O(group_size) per start
            if counts[x+k] == 0 { return false }
            counts[x+k]--                                          // L9: O(1)
        }
    }
    return true
}

final class Solution {
    func isNStraightHand(_ hand: [Int], _ groupSize: Int) -> Bool {
        if hand.count % groupSize != 0 { return false }
        var counts: [Int: Int] = [:]
        for card in hand { counts[card, default: 0] += 1 }
        var heap = BinaryHeap<Int>(hasHigherPriority: <)
        for card in counts.keys { heap.insert(card) }
        while let start = heap.peek {
            for value in start..<(start + groupSize) {
                guard let count = counts[value], count > 0 else { return false }
                counts[value] = count - 1
            }
            while let smallest = heap.peek, counts[smallest] == 0 { _ = heap.removeRoot() }
        }
        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.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

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

func isNStraightHand(hand []int, groupSize int) bool {
    if len(hand)%groupSize != 0 { return false }
    counts := make(map[int]int)
    for _, v := range hand { counts[v]++ }
    keys := make([]int, 0, len(counts))
    for k := range counts { keys = append(keys, k) }
    sort.Ints(keys)
    for _, x := range keys {
        c := counts[x]
        if c == 0 { continue }
        for k := 0; k < groupSize; k++ {
            if counts[x+k] < c { return false }
            counts[x+k] -= c
        }
    }
    return true
}

# 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()

function isNStraightHand(hand: number[], groupSize: number): boolean {
    if (hand.length % groupSize !== 0) return false;
    const counts = new Map<number, number>();
    for (const v of hand) counts.set(v, (counts.get(v) ?? 0) + 1);
    const keys = Array.from(counts.keys()).sort((a, b) => a - b);
    for (const x of keys) {
        const c = counts.get(x)!;
        if (c === 0) continue;
        for (let k = 0; k < groupSize; k++) {
            const cur = counts.get(x + k) ?? 0;
            if (cur < c) return false;
            counts.set(x + k, cur - c);
        }
    }
    return true;
}

console.assert(isNStraightHand([1,2,3,6,2,3,4,7,8], 3) === true);
console.assert(isNStraightHand([1,2,3,4,5], 4) === false);
console.assert(isNStraightHand([1], 1) === true);           // single card, group of 1
console.assert(isNStraightHand([1,2,3], 3) === true);       // exact one group
console.assert(isNStraightHand([1,2,4], 3) === false);      // gap, can't form run
console.assert(isNStraightHand([1,1,2,2,3,3], 3) === true); // two complete groups
console.log("all tests pass");

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

Greedy Exchange Arguments, proof tactics for showing that a greedy choice can be swapped into an optimal solution without making it worse.
Sorting as Preprocessing, order-first tactics that pay O(n log n) so adjacency, monotonic movement, or greedy choice becomes visible.

846. Hand of Straights (Medium)

Problem

Try it yourself

Approach 1: Brute force, try every partitioning

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

Approach 3: Min-heap + lazy consumption

Summary

Test cases

Related data structures

Related concepts