In this guide, you will get 846. Hand of Straights LeetCode Solution with the best time and space complexity. The solution to Hand of Straights problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Complexity Analysis
Time Complexity: O(m\log m + mk), where m = # of different nums
Space Complexity: O(m)
846. Hand of Straights LeetCode Solution in C++
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
map<int, int> count;
for (const int card : hand)
++count[card];
for (const auto& [start, _] : count) {
const int value = count[start];
if (value > 0)
for (int i = start; i < start + groupSize; ++i) {
count[i] -= value;
if (count[i] < 0)
return false;
}
}
return true;
}
}; /* code provided by PROGIEZ */
846. Hand of Straights LeetCode Solution in Java
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
TreeMap<Integer, Integer> count = new TreeMap<>();
for (final int card : hand)
count.merge(card, 1, Integer::sum);
for (final int start : count.keySet()) {
final int value = count.getOrDefault(start, 0);
if (value > 0)
for (int i = start; i < start + groupSize; ++i)
if (count.merge(i, -value, Integer::sum) < 0)
return false;
}
return true;
}
} // code provided by PROGIEZ
846. Hand of Straights LeetCode Solution in Python
class Solution:
def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
count = collections.Counter(hand)
for start in sorted(count):
value = count[start]
if value > 0:
for i in range(start, start + groupSize):
count[i] -= value
if count[i] < 0:
return False
return True # code by PROGIEZ
