Course4all
Join us on telegram
Home/dsa/Greedy/Hand of Straights

Hand of Straights

Master this topic with zero to advance depth.

Hand of Straights

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 and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Visual Representation

Hand: [1,2,3,6,2,3,4,7,8], Size: 3 1. Smallest is 1. Start group: [1, 2, 3]. Remaining: [6, 2, 3, 4, 7, 8] 2. Smallest is 2. Start group: [2, 3, 4]. Remaining: [6, 7, 8] 3. Smallest is 6. Start group: [6, 7, 8]. Remaining: [] Result: True
Medium

Examples

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

Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible ways to group the cards. For each card, either start a new group or add it to an existing incomplete group. This is highly inefficient but follows the core requirement.

Thought Process

  1. solve(remaining_cards): Pick a card and try to form a group of groupSize starting with it.
  2. Recurse with the remaining cards.
  3. If all cards are used, return true.

Pattern: Brute Force / Backtracking

⏱ O(N!) or O(N^N).💾 O(N)

Detailed Dry Run

Hand: [1,2,3,4], Size: 2

  • Try [1,2], left [3,4].
  • Try [3,4], left []. Success.
java
// Brute Force Code: Exponential O(N!)
// Try all permutations of groups.
Approach 2

Level II: Sorting + Simulation (O(N^2))

Intuition

Sort the hand first. Then, repeatedly find the smallest card and try to form a group of size groupSize starting from it by searching for subsequent cards in the array.

Thought Process

  1. Sort hand.
  2. Use a boolean array used to mark cards.
  3. For each i from 0 to n-1:
    • If !used[i]:
      • Mark used[i] = true. This is the start of a group.
      • Search for hand[i]+1, hand[i]+2, ..., hand[i]+groupSize-1 in the remaining array.
      • If any card is not found or already used, return false.

Pattern: Sorting and Linear Scanning

⏱ O(N^2).💾 O(N) for used array.

Detailed Dry Run

Hand: [1,2,2,3,3,4], Size: 3. Sorted: [1,2,2,3,3,4]

  1. Start with 1. Find 2 (idx 1) and 3 (idx 3). Mark used. [X, X, 2, X, 3, 4]
  2. Next unused is 2. Find 3 (idx 4) and 4 (idx 5). Mark used. [X, X, X, X, X, X] Success.
java
public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Arrays.sort(hand);
        boolean[] used = new boolean[hand.length];
        for (int i = 0; i < hand.length; i++) {
            if (used[i]) continue;
            int next = hand[i];
            used[i] = true;
            for (int k = 1; k < groupSize; k++) {
                boolean found = false;
                for (int j = i + 1; j < hand.length; j++) {
                    if (!used[j] && hand[j] == next + 1) {
                        used[j] = true;
                        next = hand[j];
                        found = true;
                        break;
                    }
                }
                if (!found) return false;
            }
        }
        return true;
    }
}
Approach 3

Level III: Optimal Greedy (TreeMap/Frequency Map)

Intuition

To form consecutive groups, every 'start' of a group must be the smallest available card. If we always start groups with the smallest remaining card, we either succeed or hit a card that cannot complete a group.

Thought Process

  1. Count frequencies of all cards.
  2. Sort unique cards (using a TreeMap or sorted keys).
  3. For each card CC that still has remaining counts:
    • It MUST be the start of count[C] groups.
    • Each such group requires cards C+1,C+2,...,C+groupSize−1C+1, C+2, ..., C+groupSize-1.
    • If any of these cards have fewer counts than count[C], return false.
    • Decrement counts of all cards in the group.

Pattern: Greedy Frequency Grouping

⏱ O(N log N) for sorting/map operations.💾 O(N) for map.

Detailed Dry Run

Hand: [1,2,2,3,3,4], Size: 3 Map: {1:1, 2:2, 3:2, 4:1}

  1. Smallest is 1. Count=1. Start group [1,2,3]. Map becomes: {1:0, 2:1, 3:1, 4:1}
  2. Next smallest is 2. Count=1. Start group [2,3,4]. Map becomes: {2:0, 3:0, 4:0} Result: True.
java
import java.util.*;

public class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int h : hand) map.put(h, map.getOrDefault(h, 0) + 1);
        
        for (int h : map.keySet()) {
            int count = map.get(h);
            if (count > 0) {
                for (int i = 0; i < groupSize; i++) {
                    if (map.getOrDefault(h + i, 0) < count) return false;
                    map.put(h + i, map.get(h + i) - count);
                }
            }
        }
        return true;
    }
}
← Previous QuestionTwo City Scheduling
Next Question →Minimum Initial Energy to Finish Tasks