{x}
blog image

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 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/

Solution Explanation for Hand of Straights

This problem asks whether a hand of cards can be divided into groups of consecutive numbers, each group having a specified size (groupSize). The solution involves efficient counting and sorting.

Core Idea:

The optimal approach leverages a hash map (or dictionary) to count card occurrences and sorting to efficiently iterate through the cards. We iterate through the sorted hand. For each card, we check if we can form a group starting with that card. If we can't (a needed consecutive card is missing or has insufficient count), we immediately return false. If we successfully form a group, we update the counts accordingly. If we process all cards and successfully create groups, we return true.

Algorithm:

  1. Count Card Occurrences: Use a hash map (like Counter in Python or HashMap in Java) to count the occurrences of each card value.
  2. Sort the Hand: Sort the hand of cards in ascending order (this makes it easier to check for consecutive numbers).
  3. Iterate and Check Groups: Iterate through the sorted hand. For each card:
    • If the card's count is greater than 0:
      • Try to form a group of groupSize consecutive cards starting with this card. Check if each consecutive card exists and has a count greater than 0.
      • If a consecutive card is missing or has insufficient count, return false.
      • If the group is successfully formed, decrement the counts of all cards in the group.
  4. Return True: If the loop completes without returning false, it means all cards were successfully grouped, so return true.

Time Complexity Analysis:

  • Counting: O(N), where N is the number of cards, to iterate through the hand and count card occurrences.
  • Sorting: O(N log N) in the worst case for sorting the hand. Many languages provide efficient sorting algorithms (like merge sort or quicksort).
  • Iteration and Group Check: O(N) in the worst case. We iterate through the sorted hand (at most N cards). Checking for the group takes O(groupSize) which is a constant since groupSize is relatively small compared to N.
  • Overall: The dominant factor is sorting, giving us a time complexity of O(N log N).

Space Complexity Analysis:

  • The hash map to store card counts takes O(N) space in the worst case (all cards are unique).
  • The space used by the sorted array might be O(N) depending on the implementation of sorting.
  • Overall space complexity is O(N).

Code Examples (Python, Java, C++, Go, TypeScript): Refer to the code blocks in the original markdown response. The Python, Java, and C++ examples use similar structures, efficiently utilizing hash maps and sorting for optimal performance. Go utilizes its map and sort and TypeScript relies on its object and array handling.

Solution 2 (Using Sorted Map/Dictionary): The second solution utilizes a sorted map (like SortedDict in Python or TreeMap in Java). The sorted nature of the map avoids explicit sorting, trading off the O(N log N) sorting for the O(N log N) of insertions into the sorted map, reducing operations for group checking. The asymptotic complexity remains O(N log N), but constant factors can differ. In cases where the input data is already roughly sorted or groupSize is relatively small compared to N, the second method might show slight advantages in some implementations.