3.28 Hand of Straights

3.28.1 Problem Metadata

3.28.2 Description

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

3.28.3 Examples

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3], [2,3,4], [6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand cannot be rearranged into groups of 4.

3.28.4 Constraints

  • \(1 \le hand.length \le 10^4\)
  • \(0 \le hand[i] \le 10^9\)
  • \(1 \le groupSize \le hand.length\)

3.28.5 Solution - Greedy with Sorted TreeMap

3.28.5.1 Walkthrough

The greedy insight is: always try to form a group starting from the smallest available card. If the smallest card cannot start a valid consecutive group of size groupSize, it is impossible to rearrange the hand.

Core Observations:

  1. Early exit: If hand.length % groupSize != 0, grouping is impossible.
  2. Always consume the minimum: Use a TreeMap (sorted by key) so firstKey() always gives the smallest unused card.
  3. Consecutive group validation: Starting from the smallest card start, check that cards start, start+1, ..., start+groupSize-1 all exist with sufficient frequency, then decrement (and remove if zero) each.

Algorithm:

  1. Build a frequency map using TreeMap<Integer, Integer>.
  2. While the map is non-empty, get the smallest key start.
  3. Call isStraightBySize(map, start, groupSize):
    • Iterate i from start to start + groupSize - 1.
    • If i is missing from the map, return false.
    • Decrement its count; remove the entry if count reaches 0.
  4. If any group fails, return false. Otherwise return true.

Example Walkthrough: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

  1. Frequency map: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}
  2. Iteration 1 — start = 1: consume 1,2,3 → map becomes {2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
  3. Iteration 2 — start = 2: consume 2,3,4 → map becomes {6:1, 7:1, 8:1}
  4. Iteration 3 — start = 6: consume 6,7,8 → map is empty
  5. Result: true

3.28.5.2 Analysis

  • Time Complexity: O(n log n) where n is the number of cards
    • Building the frequency map: O(n log n) for n TreeMap insertions
    • Each card is visited exactly once across all group iterations: O(n log n) for map operations
  • Space Complexity: O(n) for the frequency map storing at most n distinct values

3.28.5.3 Implementation Steps

  1. Return false if hand.length % groupSize != 0.
  2. Build a TreeMap frequency map over all cards.
  3. While the map is non-empty, extract firstKey() as the group start.
  4. In isStraightBySize, iterate groupSize consecutive values; return false if any is missing.
  5. Decrement each card’s count and remove it from the map when it reaches 0.
  6. Return true after all groups are formed successfully.

3.28.5.4 Java Code

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int len = hand.length;

        // Total cards must divide evenly into groups
        if (len % groupSize != 0) {
            return false;
        }

        // TreeMap keeps keys in sorted order so firstKey() always gives the smallest card
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();

        for (int num : hand) {
            int freq = freqMap.getOrDefault(num, 0);
            freqMap.put(num, ++freq);
        }

        while (!freqMap.isEmpty()) {
            // Greedy: always start the next group from the smallest remaining card
            int start = freqMap.firstKey();
            if (!isStraightBySize(freqMap, start, groupSize)) {
                return false;
            }
        }

        return true;
    }

    // Attempts to consume one consecutive group of `size` cards starting at `start`.
    // Decrements counts in-place and removes exhausted entries.
    // Returns false if any required card is missing.
    private boolean isStraightBySize(TreeMap<Integer, Integer> map, int start, int size) {
        for (int i = start; i < start + size; i++) {
            // Every card in the consecutive range must exist
            if (!map.containsKey(i)) {
                return false;
            }

            int freq = map.get(i);
            map.put(i, --freq);

            // Remove the entry once all copies of this card are used up
            if (freq == 0) {
                map.remove(i);
            }
        }

        return true;
    }
}

3.28.6 Solution - Greedy with HashMap + Stream Sort

3.28.6.1 Walkthrough

Same greedy strategy as the TreeMap solution, but separates frequency counting (HashMap) from sorted iteration (one-time sort of unique keys). This avoids the per-operation log overhead of TreeMap since the sort happens only once upfront.

Key difference: Instead of firstKey() driving group starts dynamically, we pre-sort the distinct keys and iterate them in order. A key whose count has already been reduced to 0 by a prior group is simply skipped.

Algorithm:

  1. Build a HashMap frequency map in O(n).
  2. Extract and sort the distinct keys once in O(k log k), where k is the number of distinct values.
  3. For each key in sorted order:
    • If its count is already 0, skip (consumed by an earlier group).
    • Otherwise, let count = freqMap[key] — this many groups must start here.
    • For each of the groupSize consecutive values starting at key, subtract count from their frequency. If any value has fewer than count copies, return false.
  4. Return true if all keys are processed successfully.

Example Walkthrough: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

  1. Frequency map: {1:1, 2:2, 3:2, 4:1, 6:1, 7:1, 8:1}
  2. Sorted keys: [1, 2, 3, 4, 6, 7, 8]
  3. key=1, count=1: subtract 1 from 1,2,3 → {1:0, 2:1, 3:1, 4:1, 6:1, 7:1, 8:1}
  4. key=2, count=1: subtract 1 from 2,3,4 → {2:0, 3:0, 4:0, 6:1, 7:1, 8:1}
  5. key=3, count=0: skip
  6. key=4, count=0: skip
  7. key=6, count=1: subtract 1 from 6,7,8 → {6:0, 7:0, 8:0}
  8. Result: true

3.28.6.2 Analysis

  • Time Complexity: O(n + k log k) where n is the number of cards and k is the number of distinct values
    • Building the frequency map: O(n)
    • Sorting distinct keys: O(k log k)
    • Processing all groups: O(n) total across all keys
    • Since k \(\le\) n, this is O(n log n) worst case but faster in practice than TreeMap
  • Space Complexity: O(k) for the frequency map and keys array, where k \(\le\) n

3.28.6.3 Implementation Steps

  1. Return false if hand.length % groupSize != 0.
  2. Build a HashMap frequency map over all cards.
  3. Extract distinct keys, sort them via stream.
  4. For each key in sorted order, skip if its count is 0.
  5. Otherwise subtract that count from all groupSize consecutive values; return false if any value has insufficient count.
  6. Return true after processing all keys.

3.28.6.4 Java Code

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

        // HashMap for O(n) frequency counting (no sorted-order overhead)
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : hand) {
            freqMap.merge(num, 1, Integer::sum);
        }

        // Sort distinct keys once — O(k log k) instead of per-operation TreeMap cost
        int[] keys = freqMap.keySet().stream().mapToInt(i -> i).sorted().toArray();

        for (int key : keys) {
            int count = freqMap.getOrDefault(key, 0);

            // Skip keys already fully consumed by earlier groups
            if (count == 0) {
                continue;
            }

            // `count` groups must start at this key; consume `count` copies of each
            // consecutive card in the group
            for (int i = key; i < key + groupSize; i++) {
                if (freqMap.getOrDefault(i, 0) < count) {
                    // Not enough cards to complete all groups starting at `key`
                    return false;
                }
                freqMap.merge(i, -count, Integer::sum);
            }
        }

        return true;
    }
}