Hand of Straights

medium greedy hash-map sorting

Problem

Given an array of integers hand and an integer groupSize, return true if the hand can be partitioned into groups of size groupSize where each group is a run of consecutive integers.

Inputhand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Outputtrue

Partition into [1,2,3], [2,3,4], [6,7,8].

input

from collections import Counter

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

function isNStraightHand(hand, groupSize) {
  if (hand.length % groupSize) return false;
  const count = new Map();
  for (const x of hand) count.set(x, (count.get(x) || 0) + 1);
  const keys = [...count.keys()].sort((a, b) => a - b);
  for (const x of keys) {
    const c = count.get(x);
    if (c === 0) continue;
    for (let k = 0; k < groupSize; k++) {
      if ((count.get(x + k) || 0) < c) return false;
      count.set(x + k, count.get(x + k) - c);
    }
  }
  return true;
}

import java.util.*;
class Solution {
  public boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;
    TreeMap<Integer,Integer> count = new TreeMap<>();
    for (int x : hand) count.merge(x, 1, Integer::sum);
    for (int x : new ArrayList<>(count.keySet())) {
      int c = count.getOrDefault(x, 0);
      if (c == 0) continue;
      for (int k = 0; k < groupSize; k++) {
        if (count.getOrDefault(x + k, 0) < c) return false;
        count.merge(x + k, -c, Integer::sum);
      }
    }
    return true;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize) return false;
        map<int,int> count;
        for (int x : hand) count[x]++;
        for (auto &[x, _] : count) {
            int c = count[x];
            if (c == 0) continue;
            for (int k = 0; k < groupSize; k++) {
                if (count[x + k] < c) return false;
                count[x + k] -= c;
            }
        }
        return true;
    }
};

Explanation

We want to deal the hand into groups of groupSize consecutive cards like [2,3,4]. The greedy insight is that the smallest remaining card must start a group, since no smaller card exists to lead a run that includes it.

First a fast reject: if the hand size is not divisible by groupSize, the cards cannot split evenly, so return False. Then we count every card with a Counter.

Going through cards in sorted order, for the smallest leftover value x with c copies we must build c runs starting at x. That requires at least c copies of each of x, x+1, ..., x+groupSize-1. If any is missing (count[x+k] < c) we return False; otherwise we subtract c from each of those values.

It is safe because the lowest card has only one possible role — leading a group — so committing it together with the next consecutive cards is forced, never a guess.

Example: hand=[1,2,3,6,2,3,4,7,8], groupSize=3. Smallest is 1, so form 1,2,3; next smallest left is 2, forming 2,3,4; finally 6,7,8. All cards are used, so the answer is true.

Time: O(n log n) Space: O(n)