Leetcode 846: Hand of Straights
Alice has a set of cards, each with a value written on it. She wants to rearrange these cards into groups, where each group consists of
groupSize consecutive cards. Given an integer array hand where hand[i] represents the value on the ith card, and an integer groupSize, return true if she can rearrange the cards into groups of consecutive numbers, or false otherwise.Problem
Approach
Steps
Complexity
Input: You are given an integer array `hand` representing the values on the cards and an integer `groupSize` that denotes the required group size.
Example: Input: hand = [10, 12, 13, 11, 14, 15, 16], groupSize = 3
Constraints:
• 1 <= hand.length <= 10^4
• 0 <= hand[i] <= 10^9
• 1 <= groupSize <= hand.length
Output: Return `true` if it is possible to rearrange the cards into consecutive groups of size `groupSize`. Otherwise, return `false`.
Example: Output: true
Constraints:
• If the length of `hand` is not divisible by `groupSize`, return `false`.
Goal: The goal is to determine if we can group the cards into valid groups of consecutive numbers of size `groupSize`.
Steps:
• Step 1: Count the frequency of each card in the hand using a map.
• Step 2: For each unique card, attempt to form a group by selecting consecutive cards. Decrease their frequencies as you form groups.
• Step 3: If at any point, forming a group is not possible (e.g., not enough consecutive cards), return false.
• Step 4: If all cards are grouped successfully, return true.
Goal: We must ensure that the solution can handle the large input size and check for possible groupings efficiently.
Steps:
• The length of `hand` must be divisible by `groupSize`.
• Each card in the hand must have a value greater than or equal to 0.
Assumptions:
• The hand contains at least one card.
• The values on the cards are non-negative integers.
• Input: Input: hand = [10, 12, 13, 11, 14, 15, 16], groupSize = 3
• Explanation: The hand can be rearranged into three groups: [10, 11, 12], [13, 14, 15], and [16]. Therefore, the answer is `true`.
• Input: Input: hand = [1, 2, 3, 4, 5], groupSize = 4
• Explanation: The length of the hand is 5, which is not divisible by 4, so it's impossible to divide the cards into groups of 4. Therefore, the answer is `false`.
• Input: Input: hand = [1, 2, 3, 4, 6, 7], groupSize = 3
• Explanation: It's not possible to form the required groups because the card with value 5 is missing, which breaks the sequence. Therefore, the answer is `false`.
Approach: To solve the problem, we first count the frequency of each card and attempt to group consecutive cards by checking if each value can form a valid group with its consecutive numbers.
Observations:
• If the length of the hand is not divisible by `groupSize`, it's impossible to form valid groups.
• We need to efficiently manage card frequencies and check for possible consecutive sequences.
• This problem can be tackled using a greedy approach by starting from the smallest card value and trying to form groups of consecutive numbers.
Steps:
• Step 1: Create a frequency map of all the cards in the hand.
• Step 2: Start from the smallest card and try to form a group of consecutive cards. Decrease their frequency as you form the group.
• Step 3: Repeat the process for all remaining cards, ensuring all cards are part of a valid group.
• Step 4: If at any point a valid group cannot be formed, return `false`. Otherwise, return `true`.
Empty Inputs:
• The input cannot be empty as there must be at least one card.
Large Inputs:
• Ensure that the solution can handle large input sizes (up to 10^4 cards).
Special Values:
• If the length of the hand is not divisible by `groupSize`, return `false`.
Constraints:
• The solution must handle arrays where `groupSize` is larger than the number of unique cards efficiently.
bool isNStraightHand(vector<int>& hand, int groupSize) {
map<int, int> mp;
for(int x: hand) mp[x]++;
for(auto it: mp) {
if(mp[it.first] > 0)
for(int i = 1; i < groupSize; i++){
mp[it.first + i] -= mp[it.first];
if(mp[it.first + i] < 0)
return false;
}
mp[it.first] = 0;
}
return true;
}
1 : Function Declaration
bool isNStraightHand(vector<int>& hand, int groupSize) {
The function `isNStraightHand` takes a hand of cards and checks whether the cards can be grouped into valid straight sequences of the specified size.
2 : Variable Initialization
map<int, int> mp;
A map `mp` is initialized to store the count of each card in the hand.
3 : Counting Elements
for(int x: hand) mp[x]++;
For each card in the hand, increment its count in the map `mp`.
4 : Loop Through Map
for(auto it: mp) {
Iterate over each card in the map `mp`.
5 : Condition Check
if(mp[it.first] > 0)
Check if the current card has not been used already.
6 : Inner Loop
for(int i = 1; i < groupSize; i++){
Loop through the group size and check if the following cards can form a valid group.
7 : Card Deduction
mp[it.first + i] -= mp[it.first];
Decrease the count of the card in the map for each card that should be part of the current group.
8 : Negative Count Check
if(mp[it.first + i] < 0)
If any card required for the group has a negative count, it means the group cannot be formed, so return false.
9 : Return False
return false;
Return false if the cards cannot form a valid straight hand.
10 : Reset Card Count
mp[it.first] = 0;
Set the current card count to 0 after processing it.
11 : Return True
return true;
Return true if all cards can be grouped into valid straight hands.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting of cards, which is O(n log n), followed by the greedy approach to form groups in O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the frequency map storing the count of each unique card.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus