Hand of Straights

Hand of Straights looks like a card game puzzle. But it is really a test of one idea. Can you always make the safest move first and trust it? That habit is called greedy thinking. The interviewer wants to see if you can spot the one move that can never go wrong.

🎯 The Problem

You get a hand of cards and a group size, and must split the hand into valid groups.

• Each card is just a number.
• Every group must have exactly the group-size many cards.
• The cards in each group must be consecutive numbers, like 1, 2, 3.
• Every card must be used.
• Return true if you can split the whole hand this way, else false.

Let us say the hand is [1, 2, 3, 6, 2, 3, 4, 7, 8] and the group size is 3. You can make [1, 2, 3], then [2, 3, 4], then [6, 7, 8]. Every card is used. Every group has three consecutive numbers. So the answer is true.

Input:  hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
Output: true

Explanation: groups are [1,2,3], [2,3,4], [6,7,8]

Here is the first quick check. If the total number of cards does not divide evenly by the group size, you can stop right away. The answer is false. You can never finish if the cards do not split cleanly.

Here is the shape of the problem. We have repeated numbers, and we want consecutive runs.

🐢 Approach 1: Try Every Grouping (Brute Force)

Try every possible way of splitting the cards into runs.

The idea:

• Pick group-size many cards. Check if they form a consecutive run.
• Remove them. Try again with what is left.
• If you get stuck, go back and try a different grouping.

Why it is weak:

• The number of ways to pick groups explodes as the hand grows.
• You end up trying a huge number of combinations.
• The back-and-forth retry logic is also hard to write correctly.

Here is a backtracking version of the brute-force idea:

from collections import Counter


def is_n_straight_hand(hand, group_size):
    count = Counter(hand)

    def dfs(groups_left):
        if groups_left == 0:
            return True
        start = min(num for num in count if count[num] > 0)
        for num in range(start, start + group_size):
            if count[num] == 0:
                return False
            count[num] -= 1
        ok = dfs(groups_left - 1)
        for num in range(start, start + group_size):
            count[num] += 1
        return ok

    return len(hand) % group_size == 0 and dfs(len(hand) // group_size)

⚡ Approach 2: Greedy With a Sorted Count Map (Better)

The idea in one line: the smallest leftover card must start a group, so build runs from the smallest upward.

The idea:

• Look at the smallest leftover card. No card is smaller, so nothing can sit before it in a run.
• The only group it can belong to is one that starts with it.
• So take the smallest card and build the one run it can start.

How it works:

• Use a count map that stores each card number and how many copies remain.
• Do not move cards around. Just lower the count as you use them.
• Walk the card numbers in sorted order. For each number still left, treat it as a group start.
• Try to take one of each of the next numbers in the run. If any is gone, return false.

Why it is safe:

• You always start from the smallest leftover card.
• There is never a better first move, so the greedy choice can never go wrong.
• The cost is mostly the sorting, so O(n log n).

Here is the sorted-count-map code:

from collections import Counter


def is_n_straight_hand(hand, group_size):
    count = Counter(hand)
    for start in sorted(count):
        while count[start] > 0:
            for num in range(start, start + group_size):
                if count[num] == 0:
                    return False
                count[num] -= 1
    return True

🧭 Approach 3: Greedy With a Min-Heap (Alternative)

The idea in one line: keep the distinct card values in a min-heap so the smallest is always on top.

The idea:

• A min-heap is a structure where the smallest item is always on top.
• Pull the smallest leftover card from the top each time.
• It still starts the next group, same greedy rule as before.

How it works:

• Build a count map and a min-heap of the distinct values.
• Take the heap top as the group start. Lower the count of each value in the run.
• When a value’s count hits zero, it must be the current heap top or a hole would be left behind, so check that and pop it.

Why it is an alternative:

• Same O(n log n) time as the sorted map. The heap replaces the sort.
• It reads cleanly when you only need the running smallest, not a full sorted list.
• This is the version shown in the Python code below.

Here is a dry run of the greedy steps on our example. We sort the unique numbers, then build runs from the smallest.

Steps to Solve

1. If the total card count does not divide evenly by the group size, return false right away.
2. Build a count map that stores each card number and how many copies you have.
3. Get the card numbers in sorted order.
4. Walk through the sorted numbers. For each number that still has a count above zero, treat it as the start of a group.
5. For that start number, try to remove one of each of the next numbers in the run, up to the group size.
6. If any needed number is missing or runs out, return false.
7. If you finish using every card, return true.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int isStraightHand(int hand[], int n, int groupSize) {
    if (n % groupSize != 0) return 0;   // cannot split evenly

    qsort(hand, n, sizeof(int), cmp);   // sort ascending

    // use a map from value to remaining count via offset array
    int minv = hand[0], maxv = hand[n - 1];
    int range = maxv - minv + 1;
    int *count = (int *)calloc(range, sizeof(int));
    for (int i = 0; i < n; i++) count[hand[i] - minv]++;

    for (int v = minv; v <= maxv; v++) {
        int c = count[v - minv];
        if (c > 0) {                    // v must start c groups
            for (int k = v; k < v + groupSize; k++) {
                if (k > maxv || count[k - minv] < c) {
                    free(count);
                    return 0;           // a needed number is missing
                }
                count[k - minv] -= c;   // take c copies of each step
            }
        }
    }
    free(count);
    return 1;
}

int main(void) {
    int hand[] = {1, 2, 3, 6, 2, 3, 4, 7, 8};
    int n = 9;
    int groupSize = 3;
    printf("%s\n", isStraightHand(hand, n, groupSize) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <map>
using namespace std;

bool isStraightHand(vector<int>& hand, int groupSize) {
    if (hand.size() % groupSize != 0) return false;  // cannot split evenly

    map<int, int> count;                 // value -> remaining count (sorted)
    for (int c : hand) count[c]++;

    for (auto& entry : count) {
        int value = entry.first;
        int c = count[value];
        if (c > 0) {                     // value must start c groups
            for (int k = value; k < value + groupSize; k++) {
                if (count[k] < c) return false;  // a needed number is missing
                count[k] -= c;           // take c copies of each step
            }
        }
    }
    return true;
}

int main() {
    vector<int> hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
    int groupSize = 3;
    cout << (isStraightHand(hand, groupSize) ? "true" : "false") << endl;
    return 0;
}

true

import java.util.TreeMap;
import java.util.Map;

public class HandOfStraights {
    public static boolean isStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;  // cannot split evenly

        TreeMap<Integer, Integer> count = new TreeMap<>();  // value -> count
        for (int c : hand) count.merge(c, 1, Integer::sum);

        while (!count.isEmpty()) {
            int start = count.firstKey();   // smallest leftover card
            for (int k = start; k < start + groupSize; k++) {
                Integer have = count.get(k);
                if (have == null) return false;  // needed number is missing
                if (have == 1) count.remove(k);  // used the last copy
                else count.put(k, have - 1);     // use one copy
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] hand = {1, 2, 3, 6, 2, 3, 4, 7, 8};
        int groupSize = 3;
        System.out.println(isStraightHand(hand, groupSize) ? "true" : "false");
    }
}

true

from collections import Counter
import heapq


def is_straight_hand(hand, group_size):
    if len(hand) % group_size != 0:      # cannot split evenly
        return False

    count = Counter(hand)                # value -> remaining count
    min_heap = list(count.keys())        # all distinct card values
    heapq.heapify(min_heap)              # smallest value sits on top

    while min_heap:
        start = min_heap[0]              # smallest leftover card
        for k in range(start, start + group_size):
            if count[k] == 0:            # a needed number is missing
                return False
            count[k] -= 1                # use one copy of k
            if count[k] == 0:            # this value is now used up
                if k != min_heap[0]:     # but it is not the current top
                    return False         # so a hole would be left behind
                heapq.heappop(min_heap)  # remove the used-up smallest
    return True


hand = [1, 2, 3, 6, 2, 3, 4, 7, 8]
group_size = 3
print(is_straight_hand(hand, group_size))

True

function isStraightHand(hand, groupSize) {
  if (hand.length % groupSize !== 0) return false; // cannot split evenly

  const count = new Map(); // value -> remaining count
  for (const c of hand) count.set(c, (count.get(c) || 0) + 1);

  const values = [...count.keys()].sort((a, b) => a - b); // sorted values

  for (const value of values) {
    const c = count.get(value);
    if (c > 0) {
      // value must start c groups
      for (let k = value; k < value + groupSize; k++) {
        if ((count.get(k) || 0) < c) return false; // needed number missing
        count.set(k, count.get(k) - c); // take c copies of each step
      }
    }
  }
  return true;
}

const hand = [1, 2, 3, 6, 2, 3, 4, 7, 8];
const groupSize = 3;
console.log(isStraightHand(hand, groupSize));

true

Let us walk through the Python version line by line, because the heap part is the tricky bit.

First we check len(hand) % group_size. If the cards do not divide evenly, we return False at once. This saves all the later work.

Then count = Counter(hand) builds the map from each card value to how many we have. Counter does the counting for us in one line.

Next min_heap = list(count.keys()) and heapq.heapify(min_heap) give us a min heap of the distinct values. A min heap is a structure where the smallest item is always on top. So min_heap[0] is the smallest leftover card at any moment.

Inside the loop, start = min_heap[0] grabs that smallest card. It must start a group. We then loop k from start up to start + group_size. For each k we check count[k]. If it is zero, a number in the run is missing, so we return False. Otherwise we do count[k] -= 1 to use one copy.

The careful part is when count[k] becomes zero. That value is now used up. If it is the current top of the heap, we pop it with heapq.heappop. But if it is some larger value that ran out before the top did, that means a hole opened in the middle. We can never fill that hole later. So we return False. That single check keeps the greedy choice correct.

⏱️ Time and Space Complexity

The brute force tries many groupings, so its time grows in a way that becomes unusable fast. The greedy version sorts the values once and then sweeps through them. So its cost is mostly the sorting. We write that as O(n log n). The extra space is the count map, which holds at most one entry per distinct card.

🧩 Key Takeaways

• ✅ If the total cards do not divide evenly by the group size, the answer is false at once.
• ✅ The smallest leftover card must always start a group, because nothing smaller can come before it.
• ✅ Use a count map so you lower counts instead of moving cards around.
• ✅ Build each run from the start card up to the group size, and fail if any number is missing.
• ✅ This greedy choice is always safe, so the answer comes in O(n log n) time.

🚀 What’s Next?

• Merge Triplets to Form Target Triplet
• Partition Labels