Hand of Straights - Practice Coding Problems

Hand of Straights - Problem

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

Note: Each card can only be used once, and all cards must be used to form complete groups.

Input & Output

Example 1 — Basic Valid Case

$ Input: hand = [1,2,3,6,2,3], groupSize = 3

› Output: true

💡 Note: We can form two groups: [1,2,3] and [2,3,6]. Both groups have 3 consecutive cards.

Example 2 — Invalid Case

$ Input: hand = [1,2,3,4,5], groupSize = 4

› Output: false

💡 Note: We have 5 cards but need groups of 4. Since 5 is not divisible by 4, we cannot form complete groups.

Example 3 — Gap in Sequence

$ Input: hand = [1,2,3,5,6,7], groupSize = 3

› Output: false

💡 Note: We have [1,2,3] and [5,6,7]. There's a gap between 3 and 5, so we can't form groups with the available cards consecutively.

Constraints

1 ≤ hand.length ≤ 10⁴
0 ≤ hand[i] ≤ 10⁹
1 ≤ groupSize ≤ hand.length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Cards [1,2,3,6,2,3] with groupSize=3

Group Formation

Form consecutive groups of specified size

Validation

Check if all cards are used

Key Takeaway

🎯 Key Insight: Always start forming groups from the smallest available card to ensure optimal resource utilization

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use frequency counting with greedy group formation. Always start forming groups from the smallest available card value to ensure optimal usage. Best approach uses TreeMap for O(n log n) time complexity with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n!)	O(n)	Generate all possible groupings and check if each forms valid consecutive sequences
Frequency Count with Greedy Formation	O(n log n)	O(n)	Count card frequencies and greedily form consecutive groups starting from smallest values
Optimized Greedy with Priority Queue	O(n log n)	O(n)	Use sorted frequency map for optimal greedy group formation in single pass

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible ways to partition cards into groups
For each partition, check if groups have consecutive numbers
Return true if any valid partition exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Create all possible ways to group cards

Check Consecutiveness

Verify each group has consecutive numbers

Return Result

True if any valid partition found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

bool isConsecutive(int* group, int size) {
    qsort(group, size, sizeof(int), compare);
    for (int i = 1; i < size; i++) {
        if (group[i] != group[i-1] + 1) return false;
    }
    return true;
}

bool backtrackSolution(int* remaining, int remSize, int groupSize, int groupsFormed, int totalGroups) {
    if (remSize == 0) return groupsFormed == totalGroups;
    if (remSize < groupSize) return false;
    
    // Try first possible combination (simplified for demonstration)
    if (remSize >= groupSize) {
        int group[groupSize];
        for (int i = 0; i < groupSize; i++) {
            group[i] = remaining[i];
        }
        
        if (isConsecutive(group, groupSize)) {
            int newRemaining[remSize - groupSize];
            for (int i = 0; i < remSize - groupSize; i++) {
                newRemaining[i] = remaining[i + groupSize];
            }
            if (backtrackSolution(newRemaining, remSize - groupSize, groupSize, groupsFormed + 1, totalGroups)) {
                return true;
            }
        }
    }
    return false;
}

bool solution(int* hand, int handSize, int groupSize) {
    if (handSize % groupSize != 0) return false;
    qsort(hand, handSize, sizeof(int), compare);
    return backtrackSolution(hand, handSize, groupSize, 0, handSize / groupSize);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int hand[1000];
    int handSize = 0;
    char *token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            hand[handSize++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int groupSize;
    scanf("%d", &groupSize);
    
    bool result = solution(hand, handSize, groupSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generating all partitions requires factorial time complexity

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and temporary storage for partitions

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler