#846

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Hand of Straights

Check if a hand of cards can be rearranged into groups of consecutive values.

Problem Statement

Alice has a set of cards, each represented by an integer. She needs to rearrange these cards into groups, where each group contains a set of consecutive numbers and has a size equal to a given value, groupSize. Alice wants to know if it's possible to rearrange the cards into such groups, or if it's not possible.

Given an integer array hand, where hand[i] represents the value of the ith card, and an integer groupSize, your task is to determine if it is possible to rearrange the cards into groups of consecutive numbers of size groupSize. If it's possible, return true; otherwise, return false.

Examples

Example 1

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]

Example 2

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

Output: false

Alice's hand can not be rearranged into groups of 4.

Constraints

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

Solution Approach

Array Scanning and Hash Table Lookup

Start by counting the frequency of each card value using a hash table. Then, scan through the sorted card values to try and form valid groups of consecutive cards. If at any point a group cannot be formed, return false.

Greedy Grouping

Once the frequency map is built, always attempt to form the smallest consecutive group starting from the current card. Greedily pick the smallest available card and decrement its count. If the required consecutive cards are not available, the hand cannot be rearranged successfully.

Time and Space Complexity Optimization

The solution efficiently handles the problem in O(n) time, where n is the length of the input hand array. It uses a hash table to store card counts, which ensures the space complexity remains O(n). Sorting the cards ensures the groups are formed in the correct order.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n log n) due to the sorting step, where n is the number of cards in the hand. The space complexity is O(n) for storing the frequency of card values in a hash table.

What Interviewers Usually Probe

Ability to recognize and implement a greedy strategy for problem-solving.
Proficiency in using hash tables for counting and grouping elements efficiently.
Understanding the time and space trade-offs involved in array manipulation and sorting.

Common Pitfalls or Variants

Common pitfalls

Failing to check if the groupSize divides the hand length evenly, leading to incorrect results.
Not sorting the hand before attempting to form consecutive groups, causing invalid groupings.
Overlooking edge cases such as very small input sizes or input arrays with repeated values.

Follow-up variants

What if the group size is 1? This would simply require checking if the hand can be rearranged into individual groups.
What if the hand contains large gaps between card values? This may make it impossible to form consecutive groups.
What if groupSize equals the length of the hand? This forces the entire hand to be checked as a single group of consecutive values.

FAQ

How does the greedy approach work in Hand of Straights?

The greedy approach starts by forming the smallest possible consecutive group, ensuring that no card is used more than once, and all groups are valid.

What are the common mistakes in solving Hand of Straights?

Common mistakes include failing to check if groupSize divides the hand size evenly or not sorting the cards before grouping.

What is the time complexity of the Hand of Straights problem?

The time complexity is O(n log n) due to the sorting step, where n is the number of cards.

How do hash tables help in solving Hand of Straights?

Hash tables allow for efficient counting and tracking of card values, making it easy to verify if consecutive groups can be formed.

What happens if groupSize is larger than the number of cards?

If groupSize is larger than the number of cards, it's immediately impossible to form any groups, and the answer should be false.

terminal

Solution

Solution 1: Hash Table + Sorting

We first check whether the length of the array $\textit{hand}$ is divisible by $\textit{groupSize}$. If it is not, this means that the array cannot be partitioned into multiple subarrays of length $\textit{groupSize}$, so we return $\text{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        cnt = Counter(hand)
        for x in sorted(hand):
            if cnt[x]:
                for y in range(x, x + groupSize):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Solution 2: Ordered Set

Similar to Solution 1, we first check whether the length of the array $\textit{hand}$ is divisible by $\textit{groupSize}$. If it is not, this means that the array cannot be partitioned into multiple subarrays of length $\textit{groupSize}$, so we return $\text{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        cnt = Counter(hand)
        for x in sorted(hand):
            if cnt[x]:
                for y in range(x, x + groupSize):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Continue Practicing

#954 array of doubled pairs #1054 distant barcodes #632 smallest range covering elements from k lists