Scale Engineer

Hand of Straights

Med
#0800Time: O(N^2). Sorting the array takes O(N log N). The main loop iterates through N elements. Inside, for each potential group start, we might scan a large portion of the array up to `groupSize` times. This results in a time complexity dominated by the nested search, which is approximately O((N/groupSize) * groupSize * N) = O(N^2).Space: O(N), where N is the number of cards in the hand. This space is used for the `used` boolean array.
Patterns
Greedy
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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.

 

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 can not be rearranged into groups of 4.

 

Constraints:

  • 1 <= hand.length <= 104
  • 0 <= hand[i] <= 109
  • 1 <= groupSize <= hand.length

 

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first sorts the hand to make finding consecutive cards easier. It then iterates through the sorted hand, and for each card not yet used, it tries to form a new group of groupSize consecutive cards by scanning the rest of the array. A boolean array is used to keep track of cards that have been placed into a group.

Algorithm

  • First, perform a basic check: if the total number of cards hand.length is not divisible by groupSize, it's impossible to form the required groups, so return false.
  • Sort the hand array in ascending order. This makes it easier to find consecutive cards.
  • Create a boolean array used of the same size as hand, initialized to false, to keep track of which cards have been assigned to a group.
  • Iterate through the sorted hand from left to right. For each card hand[i]:
    • If the card is already used (used[i] is true), skip it.
    • If it's not used, treat it as the starting card of a new group.
    • Mark used[i] as true.
    • Now, search for the next groupSize - 1 consecutive cards (hand[i] + 1, hand[i] + 2, etc.) in the rest of the array.
    • For each required consecutive card, perform a linear scan from the current position onwards to find an available (unused) card with the correct value.
    • If a required card is found, mark it as used and continue searching for the next one in the sequence.
    • If at any point a required consecutive card cannot be found, it means a valid group cannot be formed from the current starting card. Return false.
  • If the entire hand array is traversed and all cards are successfully grouped, return true.

Walkthrough

import java.util.Arrays; class Solution {    public boolean isNStraightHand(int[] hand, int groupSize) {        int n = hand.length;        if (n % groupSize != 0) {            return false;        }         Arrays.sort(hand);        boolean[] used = new boolean[n];         for (int i = 0; i < n; i++) {            if (used[i]) {                continue;            }                        // This card starts a new group            int lastCard = hand[i];            used[i] = true;            int cardsInGroup = 1;                        // Find the rest of the group            int searchIdx = i + 1;            while (cardsInGroup < groupSize) {                int nextCardNeeded = lastCard + 1;                int foundIdx = -1;                // Linearly scan for the next card                for (int j = searchIdx; j < n; j++) {                    if (!used[j] && hand[j] == nextCardNeeded) {                        foundIdx = j;                        break;                    }                }                 if (foundIdx != -1) {                    used[foundIdx] = true;                    lastCard = hand[foundIdx];                    cardsInGroup++;                    searchIdx = foundIdx + 1; // Optimization: start next search after the found card                } else {                    // Could not find the next consecutive card                    return false;                }            }        }         return true;    }}

Complexity

Time

O(N^2). Sorting the array takes O(N log N). The main loop iterates through N elements. Inside, for each potential group start, we might scan a large portion of the array up to `groupSize` times. This results in a time complexity dominated by the nested search, which is approximately O((N/groupSize) * groupSize * N) = O(N^2).

Space

O(N), where N is the number of cards in the hand. This space is used for the `used` boolean array.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • It's a direct simulation of the grouping process.

Cons

  • Highly inefficient due to the nested loops and repeated linear scanning.

  • Will likely result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

class Solution {public  boolean isNStraightHand(int[] hand, int groupSize) {    Map<Integer, Integer> cnt = new HashMap<>();    for (int v : hand) {      cnt.put(v, cnt.getOrDefault(v, 0) + 1);    }    Arrays.sort(hand);    for (int v : hand) {      if (cnt.containsKey(v)) {        for (int x = v; x < v + groupSize; ++x) {          if (!cnt.containsKey(x)) {            return false;          }          cnt.put(x, cnt.get(x) - 1);          if (cnt.get(x) == 0) {            cnt.remove(x);          }        }      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem