Hand of Straights
You are given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize.
You want to rearrange the cards into groups so that each group is of size groupSize, and card values are consecutively increasing by 1.
Return true if it's possible to rearrange the cards in this way, otherwise, return false.
Example 1:
Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4
Output: trueExplanation: The cards can be rearranged as [1,2,3,4] and [2,3,4,5].
Example 2:
Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4
Output: falseExplanation: The closest we can get is [1,2,3,4] and [3,5,6,7], but the cards in the second group are not consecutive.
Constraints:
1 <= hand.length <= 10000 <= hand[i] <= 10001 <= groupSize <= hand.length
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.
Hint 1
It is observed that to form a group, the minimum value should be the starting value of the group. Additionally, the minimum value in the array serves as the starting value for one or more groups based on its frequency. Can you think of an efficient way to determine the frequencies of array elements? Maybe a specific data structure can be useful here.
Hint 2
We can use a hash map to store the elements along with their frequencies. Additionally, we sort the given array. Then, we iterate through the sorted array and try to form groups by decrementing the frequency count. If we fail to form a group at any step, we immediately return false. Can you think why this works?
Hint 3
Sorting ensures we start with the smallest available value, while the hash map helps track element availability using frequency counts. At each step, we pick the smallest available value x and attempt to form a group from x to x + groupSize - 1. If all elements are present based on their frequency counts, we decrement their counts as we iterate. If we successfully form all groups, we return true; otherwise, we return false.