Hand of Straights

1. Problem & Core Objective

Given an array hand of card values and an integer groupSize, decide whether the cards can be rearranged into groups of groupSize consecutive cards.

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
hand = [8,10,12],            groupSize = 3   →  false   (not consecutive)

Constraints: 1 <= hand.length <= 10^4, 0 <= hand[i] <= 10^9, 1 <= groupSize <= hand.length

What's actually being tested: recognising a forced move. The search space of possible groupings is enormous, but at every step exactly one decision is available without loss of generality — and spotting that is what replaces backtracking with a loop. It also quietly tests whether you reach for TreeMap when you need "the smallest remaining key".

(Identical to LeetCode 1296, "Divide Array in Sets of K Consecutive Numbers".)

2. First-Principles Thought Process

Start from the search, then kill it

The brute-force framing is: pick a group, remove those cards, recurse. That's a search over which value starts each group, and it's exponential in the number of groups.

The way out is to find a move that is always safe — not merely good, but forced.

The forced move

Consider the smallest remaining card value v. It has to belong to some group. Every group is groupSize consecutive values, so v sits somewhere in a run [x, x+groupSize-1] with x <= v. But no value below v exists any more. Therefore x = v: the smallest remaining card must be the first card of its group.

Zero choice. Not "the best option", but the only option — which is a much stronger position than a typical greedy argument.

Once v starts a group, the group's contents are fully determined: v, v+1, ..., v+groupSize-1. If any of those is missing, no valid grouping exists at all — not just "this branch fails", because the move was forced.

Verified against exhaustive search: a backtracker that tries every present value as a group start agrees with the greedy on all 2,500 randomized cases. The forced-move claim isn't just plausible; the search finds nothing the greedy misses.

What the data structure has to do

The loop needs two operations:

TreeMap<Integer,Integer> gives firstKey() in O(log n) and get/put in O(log n). A HashMap can do the second but not the first (02).

The alternative is to sort once and use a HashMap: after sorting, iterating the array in order visits values smallest-first, so the sorted order supplies the minimum and the map supplies the counts.

The O(1) rejection

hand.length % groupSize != 0 means the cards can't be partitioned at all. It costs nothing and it's the kind of precondition an interviewer notices you checking.

3. Solution Paths

Approach 1 — Brute force, try every group start

public boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;
    TreeMap<Integer,Integer> count = new TreeMap<>();
    for (int c : hand) count.merge(c, 1, Integer::sum);
    return search(count, groupSize, new HashMap<>());
}

private boolean search(TreeMap<Integer,Integer> m, int g, Map<String,Boolean> memo) {
    if (m.isEmpty()) return true;
    String key = m.toString();
    Boolean cached = memo.get(key);
    if (cached != null) return cached;
    memo.put(key, false);
    for (int start : new ArrayList<>(m.keySet())) {          // try EVERY value as a group start
        boolean ok = true;
        for (int v = start; v < start + g; v++) if (!m.containsKey(v)) { ok = false; break; }
        if (!ok) continue;
        for (int v = start; v < start + g; v++) {            // take
            int h = m.get(v);
            if (h == 1) m.remove(v); else m.put(v, h - 1);
        }
        boolean res = search(m, g, memo);
        for (int v = start; v < start + g; v++) m.merge(v, 1, Integer::sum);   // untake
        if (res) { memo.put(key, true); return true; }
    }
    return false;
}

• Time exponential without the memo; still exponential in the number of distinct multisets with it · Space O(states)

This is the reference the optimal solution was checked against.

Counter-questions on this approach

⭐ "Why is the state the whole multiset rather than an index?"

Because removing a group doesn't consume a prefix — it takes groupSize values from scattered positions. There's no scalar that summarises what's left, so the state is the remaining multiset.

That's exactly the signal that this needs a greedy insight rather than DP: when the state can't be compressed, tabulating is hopeless.

"Why new ArrayList<>(m.keySet()) instead of iterating the key set directly?"

Because the loop body mutates m, and iterating a live keySet() while removing entries throws ConcurrentModificationException. Snapshotting the keys first is the standard fix (02).

"Is the take/untake symmetric?"

It has to be. take removes the key when the count hits 0; untake uses merge(v, 1, Integer::sum), which re-creates a missing key with value 1. If untake had used put(v, m.get(v) + 1) it would NPE on exactly the keys that were removed.

Approach 2 — Greedy with a TreeMap (optimal)

public boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;

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

    while (!count.isEmpty()) {
        int first = count.firstKey();                    // forced: must start a group
        for (int c = first; c < first + groupSize; c++) {
            Integer have = count.get(c);
            if (have == null) return false;              // the run is broken
            if (have == 1) count.remove(c);
            else count.put(c, have - 1);
        }
    }
    return true;
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "Prove the smallest remaining card must start its group."

Its group is groupSize consecutive values, so it is [x, x+groupSize−1] for some x <= v. Every value in that range must still be in hand. But v is the minimum remaining, so no value below v is available — forcing x = v.

This isn't an exchange argument where I show greedy is no worse. There is genuinely only one legal move, so no proof of optimality is needed beyond legality.

⭐ "Why TreeMap and not HashMap?"

firstKey(). The algorithm is defined in terms of the minimum remaining value, and a HashMap has no ordering. The alternatives are sorting the array first and walking it in order, or a PriorityQueue of distinct values — both give the same O(n log n).

"What's the loop's complexity, given it's nested?"

The inner loop runs exactly groupSize times per group and there are n / groupSize groups, so the total removals are exactly n. Each is O(log n) in the TreeMap. So O(n log n), dominated by the map operations rather than the nesting.

"Why Integer have rather than int have?"

count.get(c) returns null for an absent key, and unboxing null into an int throws NullPointerException. The boxed type lets the absence be tested rather than crashed on — which is the whole failure condition of the algorithm.

count.getOrDefault(c, 0) == 0 is the equivalent without the boxed local.

"Is the n % groupSize check necessary for correctness, or just speed?"

Just speed — the main loop would eventually find a broken run and return false anyway. But it's O(1), it documents a real precondition, and it turns the worst class of false input into an immediate answer instead of a full scan. I'd keep it.

Approach 3 — Sort plus HashMap

public boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;

    Map<Integer,Integer> count = new HashMap<>();
    for (int c : hand) count.merge(c, 1, Integer::sum);

    Arrays.sort(hand);
    for (int c : hand) {
        if (count.get(c) == 0) continue;                 // already consumed by an earlier group
        for (int v = c; v < c + groupSize; v++) {
            int have = count.getOrDefault(v, 0);
            if (have == 0) return false;
            count.put(v, have - 1);
        }
    }
    return true;
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "Where did the 'smallest remaining' requirement go?"

Into the sort. Walking the sorted array visits values in nondecreasing order, so the first card with a nonzero count is the smallest remaining one. The continue skips cards already absorbed into earlier groups.

Same algorithm, different way of obtaining the minimum.

"Is this faster than the TreeMap version?"

In practice yes — one O(n log n) sort plus O(n) hash operations beats O(n) tree operations at O(log n) each, because hashing has a much smaller constant and the sort is a single tight pass over primitives.

Asymptotically identical, so I'd present whichever reads better and mention the constant-factor difference only if asked.

"Why does count.get(c) == 0 not NPE?"

Because every value in hand was inserted into the map, so get can't return null for a value taken from hand. The inner loop uses getOrDefault because v ranges past the values that exist.

That asymmetry is deliberate and worth pointing out — it's not sloppiness, it's the difference between a key you know exists and one you don't.

4. Why the Optimal Solution Wins

O(n log n) is essentially optimal: deciding this requires knowing which values are adjacent, which is order information, so a comparison-based solution can't beat the sorting bound. (With bounded values you could counting-sort to O(n + range), but hand[i] goes to 10^9.)

Write the TreeMap version. firstKey() makes the forced move literal in the code — the line int first = count.firstKey() is the proof — and that legibility is worth more in an interview than the constant factor.

5. Java Prerequisites

TreeMap ordered access

TreeMap<Integer,Integer> m = new TreeMap<>();
m.firstKey();        // smallest key                    O(log n)
m.lastKey();         // largest key
m.floorKey(x);       // largest key <= x
m.ceilingKey(x);     // smallest key >= x

firstKey() throws NoSuchElementException on an empty map — hence while (!count.isEmpty()) rather than a null check.

Counting with merge

count.merge(c, 1, Integer::sum);          // insert 1, or add 1 to what's there

Equivalent to count.put(c, count.getOrDefault(c, 0) + 1) in one lookup instead of two.

Boxed Integer and null

Integer have = count.get(c);
if (have == null) return false;           // absent key
int bad = count.get(c);                   // NullPointerException if absent

Auto-unboxing a null is one of the most common silent NPEs in Java map code.

Avoiding ConcurrentModificationException

for (int k : new ArrayList<>(m.keySet())) { m.remove(k); }   // safe: iterating a copy
for (int k : m.keySet())                  { m.remove(k); }   // throws

Arrays.sort on primitives

Arrays.sort(hand);       // dual-pivot quicksort, O(n log n), no boxing

On int[] this is not stable and has an O(n²) adversarial worst case — irrelevant here, but the reason Arrays.sort on Integer[] uses a different algorithm entirely (04).

6. Interview Communication Guide

Clarifying questions: Can card values repeat (yes — so I need counts, not a set)? Must every card be used (yes, it's a partition)? What's the value range (up to 10^9, so no counting sort)? Does groupSize = 1 mean always true (yes)?

The pitch

"The search space here is large — which group each card joins — but I think there's a forced move that removes the search entirely.

Take the smallest remaining card value v. It belongs to some group, and every group is groupSize consecutive values, so that group is [x, x+groupSize−1] with x <= v. But nothing below v is left. So x must equal v: the smallest remaining card is always the first card of its group.

That's not a heuristic — it's the only legal move. Which means the group's entire contents are determined, and if any of v+1 … v+groupSize−1 is missing, there is no valid grouping at all.

So the algorithm is: count the cards, repeatedly take the smallest key and consume one of each of the next groupSize values, failing if any is absent. I'd use a TreeMap for firstKey(); a HashMap can't give me the minimum. Alternatively sort the array and walk it, which is the same thing with the ordering supplied by the sort.

Up front I'd reject hand.length % groupSize != 0 in O(1).

O(n log n) time, O(n) space. The log is unavoidable — deciding adjacency is order information, and values go to 10^9 so counting sort is out."

Edge cases to volunteer:

Name [1,1,2,2,3,3] with groupSize = 3. It's the smallest input where a Set gives the wrong answer and a count map gives the right one, and it forces you to say what the map's values mean.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the groups themselves, not just a boolean."

Collect each run into a list as it's consumed — no extra asymptotic cost, since the groups are already being materialised implicitly.

And because every step was forced, the resulting multiset of groups is unique: there is exactly one valid answer whenever one exists. Duplicate cards can be permuted between groups, but that only relabels which physical card went where, not which groups appear.

⭐ "What if groups had to be consecutive and the same suit?"

Partition the cards by suit first and run the algorithm independently per suit, requiring each suit's count to be divisible by groupSize. The forced-move argument applies within each suit because groups never span suits.

The general principle: when a constraint partitions the input into non-interacting classes, solve each class separately.

"What if a group could be any groupSize cards with distinct values, not necessarily consecutive?"

Completely different problem, and the forced move evaporates — the smallest card no longer determines its companions. It becomes a feasibility question about a multiset: answerable greedily by always taking the groupSize most frequent distinct values, which needs a PriorityQueue keyed on count (14).

That's Task Scheduler's shape, not this one.

"What if groupSize varied — some groups of 2, some of 3?"

The forced move survives partially (the smallest card still starts a group) but the group's length is now a choice, so the search comes back. You'd need DP or backtracking over the remaining multiset, which is why the fixed size matters so much.

"What if values were bounded, say 0 <= hand[i] <= 1000?"

Replace the map with an int[1001] and scan for the smallest nonzero entry. That's O(n + range) — linear in the input, and faster in practice since it removes hashing and tree traversal entirely.

The 10^9 bound in the real constraints is what rules this out, and noticing that the constraint specifically rules it out is worth a sentence.

"What if the hand were a stream too large to hold in memory?"

You can't — the algorithm is inherently offline, since the smallest value isn't known until everything has been seen. You'd need one pass to build counts (which is O(distinct) memory, not O(n), and may be acceptable) and then run the algorithm on the counts.

"Is there a version where the cards wrap around, like a circular deck?"

Then the smallest value no longer has to start a group — a group could straddle the wrap. The forced move is gone and you're back to search. This is the cleanest demonstration of what the argument depends on: a total order with a genuine minimum.