Hand of Straights

NeetCode: Hand of Straights · LeetCode: 846. Hand of Straights · Difficulty: Medium

Given a hand of cards, each with a number, rearrange them into groups of size groupSize where each group consists of consecutive numbers. Return true if that is possible.

Example

Text

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

Brute force: sort, then build groups with used flags

The smallest unused card must start a group, because nothing smaller is left to precede it. Sort a copy of the hand and, for each unused card, scan the array for the next groupSize - 1 consecutive values and mark them used. Each search is a linear scan.

Java

import java.util.Arrays;

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (groupSize <= 0 || hand.length % groupSize != 0) {
            return false;
        }
        int[] cards = hand.clone();
        Arrays.sort(cards);
        boolean[] used = new boolean[cards.length];
        for (int i = 0; i < cards.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            int next = cards[i];
            for (int k = 1; k < groupSize; k++) {
                next++;
                int found = -1;
                for (int j = i + 1; j < cards.length; j++) {
                    if (!used[j] && cards[j] == next) {
                        found = j;
                        break;
                    }
                }
                if (found == -1) {
                    return false;
                }
                used[found] = true;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isNStraightHand(new int[]{1, 2, 3, 6, 2, 3, 4, 7, 8}, 3));
        System.out.println(s.isNStraightHand(new int[]{1, 2, 4, 2, 3, 5, 3, 6}, 4));
        System.out.println(s.isNStraightHand(new int[]{}, 3));
    }
}

Output

true
false
true

hand.clone() copies the array so the caller's array is not reordered. Time: O(n^2) (plus O(n log n) sort). Space: O(n).

Optimal: greedy over a counted, ordered map

The greedy argument is the same (the smallest remaining card must start a group), but a TreeMap<Integer, Integer> from value to count replaces the searching. A TreeMap keeps its keys in sorted order, and firstEntry() returns the smallest key in O(log n). Repeatedly take the smallest value v still present. If it has groups copies, groups groups must start there, so subtract groups from the counts of v, v+1, ..., v + groupSize - 1; if any of them is missing or too small, return false. Emptied entries are removed so the smallest value is always at the front.

Java

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

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (groupSize <= 0 || hand.length % groupSize != 0) {
            return false;
        }
        TreeMap<Integer, Integer> counts = new TreeMap<>();
        for (int c : hand) {
            counts.merge(c, 1, Integer::sum);
        }
        while (!counts.isEmpty()) {
            Map.Entry<Integer, Integer> first = counts.firstEntry();
            int start = first.getKey();
            int groups = first.getValue();
            for (int k = 0; k < groupSize; k++) {
                if (start > Integer.MAX_VALUE - k) {
                    return false; // start + k would overflow int
                }
                int v = start + k;
                Integer c = counts.get(v);
                if (c == null || c < groups) {
                    return false;
                }
                if (c == groups) {
                    counts.remove(v);
                } else {
                    counts.put(v, c - groups);
                }
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isNStraightHand(new int[]{1, 2, 3, 6, 2, 3, 4, 7, 8}, 3));
        System.out.println(s.isNStraightHand(new int[]{1, 2, 4, 2, 3, 5, 3, 6}, 4));
        System.out.println(s.isNStraightHand(new int[]{}, 3));
    }
}

Output

true
false
true

counts.merge(c, 1, Integer::sum) inserts 1 for a new key and adds 1 to an existing count. c == groups compares an Integer with an int, so c is unboxed and the comparison is by value. The overflow guard matters because start + k wraps silently in int arithmetic. Time: O(n log n): each round removes at least groupSize cards using groupSize map operations of O(log n), so there are at most n map operations in total. Space: O(n).