☕ DSA Java Articles

Topics › Heaps › Medium Problems

Hand of Straights

Medium TUF ID 556 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You hold a hand of cards, each showing an integer, and a number groupSize. Decide whether the whole hand can be split into groups where every group has exactly groupSize cards with consecutive values, like [4, 5, 6]. Every card must be used exactly once. Return true or false.

Constraints: 1 ≤ hand.length ≤ 10^4, 0 ≤ hand[i] ≤ 10^9, 1 ≤ groupSize ≤ hand.length. The same problem appears on LeetCode as “Divide Array in Sets of K Consecutive Numbers”.

Example 1

hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
answer = true            // [1, 2, 3], [2, 3, 4], [6, 7, 8]

Example 2

hand = [1, 2, 3, 4, 5], groupSize = 4
answer = false           // 5 cards cannot be split into groups of 4

Example 3

hand = [1, 1, 2, 3], groupSize = 2
answer = false           // [1, 2] works, but the other 1 would need a 2 as well

The key observation

Take the smallest card still in the hand, say x. Which group can it belong to? It cannot sit in the middle or at the end of a group, because that would require x - 1, which is smaller than every remaining card. So x must start a group, and that group must be exactly x, x + 1, ..., x + groupSize - 1.

This is not a guess that happens to work. The choice is forced, which is why the greedy is correct: if any of those values is missing, no valid split exists. Remove the group and repeat. All three approaches implement this one rule; they differ only in how quickly they find “the smallest remaining card” and “is x + i still available”.

A free check comes first: if hand.length is not a multiple of groupSize, the answer is false.

Approach 1: Brute force, sort and scan

Intuition. Sort the cards. Now the smallest unused card is simply the first unused position. From there, scan forward for an unused card equal to x + 1, then x + 2, and so on, marking each one as used. Cards with a smaller value that we pass over are duplicates waiting to start their own group later, so we leave them alone.

Algorithm.

  1. If n % groupSize != 0, return false.
  2. Sort a copy of the hand and create a used array.
  3. For each index i from left to right that is not used:
    • Mark it used. It starts a group with value a[i].
    • For the remaining groupSize - 1 members, advance a pointer j past used cards and past cards smaller than the needed value. If j runs off the end or a[j] is not the needed value, return false. Otherwise mark a[j] used and need the next value.
  4. Return true.
static boolean bruteForce(int[] hand, int groupSize) {
    int n = hand.length;
    if (n % groupSize != 0) return false;
    int[] a = hand.clone();
    Arrays.sort(a);
    boolean[] used = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;                      // smallest unused card: it must start a group
        int need = a[i] + 1, j = i + 1;
        for (int taken = 1; taken < groupSize; taken++) {
            while (j < n && (used[j] || a[j] < need)) j++;
            if (j == n || a[j] != need) return false;
            used[j] = true;
            need++;
            j++;
        }
    }
    return true;
}

Complexity. Time O(n^2) in the worst case: each group’s scan can walk over many cards that earlier groups already used. Sorting adds O(n log n). Space O(n) for the copy and the used array.

The waste is the rescanning. A card that was used long ago is skipped again and again by later groups.

Approach 2: Better, count map plus min-heap

Intuition. Instead of tracking individual cards, track how many copies of each value remain, in a hash map. A min-heap of the distinct values gives the smallest remaining value in O(1). To form a group starting at first = heap.peek(), decrement the counts of first, first + 1, ..., first + groupSize - 1. If any count is already zero, return false.

When a value’s count drops to zero it must leave the heap. A PriorityQueue can only remove its top cheaply, so we insist that the exhausted value is the top. If it is not, some smaller value u still has cards left. The next group must start at the smallest value, which is at most u, and that group would need the value that just ran out. So returning false right there is correct, and it keeps the heap and the map consistent.

Algorithm.

  1. If n % groupSize != 0, return false.
  2. Count every value in a map, and build a min-heap of the distinct values.
  3. While the heap is not empty:
    • Let first = heap.peek().
    • For v from first to first + groupSize - 1: read c = count[v]. If c == 0, return false. Store c - 1. If that made the count zero, v must equal the heap top; if not, return false, otherwise pop it.
  4. Return true.
static boolean minHeap(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);
    PriorityQueue<Integer> pq = new PriorityQueue<>(count.keySet());
    while (!pq.isEmpty()) {
        int first = pq.peek();
        for (int v = first; v < first + groupSize; v++) {
            int c = count.getOrDefault(v, 0);
            if (c == 0) return false;
            count.put(v, c - 1);
            if (c == 1) {                    // v is used up: it must be the smallest value left
                if (v != pq.peek()) return false;
                pq.poll();
            }
        }
    }
    return true;
}

Complexity. Time O(n log n). There are n / groupSize groups and each does groupSize map updates, so n map operations in total. Each distinct value is pushed and popped once at O(log n). Space O(n) for the map and the heap.

This is the version usually expected under the “Heaps” heading. A TreeMap with firstKey() would work the same way, at the same cost.

Approach 3: Optimal, walking back to the start of a run

Intuition. We do not actually need the global minimum. The argument in the key observation works for any value start whose predecessor start - 1 has no cards left. Such a card cannot be in the middle of a group, so every remaining copy of start must open its own group. If start has g copies left, we can open all g groups at once by subtracting g from the counts of start, start + 1, ..., start + groupSize - 1.

How do we find such a value without sorting? Take any card from the input and walk downward while the predecessor still has cards. Where the walk stops is the start of that card’s run of consecutive values. Then process the run upward: after start is cleared, start + 1 has no remaining predecessor either, so it is the next start, and so on up to the card we began from.

This is the same “find the start of a run with a hash lookup” trick used in Longest Consecutive Sequence.

Algorithm.

  1. If n % groupSize != 0, return false. Count every value in a hash map.
  2. For each card in the hand (in input order):
    • Set start = card, and decrease start while count[start - 1] > 0.
    • For start from there up to card: let groups = count[start]. If it is zero, skip. Otherwise, for every v from start to start + groupSize - 1, if count[v] < groups return false, else subtract groups.
  3. Return true.
static boolean optimal(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);
    for (int card : hand) {
        int start = card;
        while (count.getOrDefault(start - 1, 0) > 0) start--;   // nothing below start is left
        for (; start <= card; start++) {
            int groups = count.getOrDefault(start, 0);         // every remaining card here opens a group
            if (groups == 0) continue;
            for (int v = start; v < start + groupSize; v++) {
                int have = count.getOrDefault(v, 0);
                if (have < groups) return false;
                count.put(v, have - groups);
            }
        }
    }
    return true;
}

Dry run on example 1, starting counts {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}, groupSize = 3:

card walk back to groups opened counts afterwards
1 1 1 at value 1 → [1, 2, 3] {2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
2 2 (count of 1 is now 0) 1 at value 2 → [2, 3, 4] {6:1, 7:1, 8:1}
3 3 none, count of 3 is 0 unchanged
6 6 1 at value 6 → [6, 7, 8] all zero
2, 3, 4, 7, 8   none all zero

Every count reached zero without a shortage, so the answer is true.

Complexity. Time O(n) expected. The downward walk only passes over values that still have cards, and every one of those values is cleared by the upward loop that follows, so each value is walked over at most once. Each subtraction loop opens at least one group and costs groupSize steps; there are only n / groupSize groups, so all subtraction loops together cost O(n). Space O(n) for the map.

Edge cases and pitfalls