# Solution For Hand Of Straights

The problem “Hand of Straights” on LeetCode is stated as follows:

You are given an array of integers hand representing the cards you have. Each integer in hand represents a card of the corresponding value. The value of each card ranges from 1 to W where W is the maximum value of any card in hand.

You want to rearrange the cards in the hand into groups so that each group has W cards, and no two cards of the same value are in the same group. You can rearrange the cards in any way you like, but you must rearrange all the cards.

Return true if it is possible to rearrange the cards as described, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3

Output: true

Explanation: You can split the hand into [1,2,3], [2,3,4], [6,7,8].

Example 2:

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

Output: false

Explanation: There is no way to split the hand into groups of 4.

The problem can be solved using a hash map and a priority queue. The steps involved in the solution are as follows:

- First, we count the frequency of each card using a hash map. We can do this in O(n) time complexity where n is the number of cards.
- Next, we initialize a priority queue with the keys of the hash map. We can use a priority queue because we want to process the cards in ascending order of value.
- Now we start processing the cards. We take out the smallest card from the priority queue and try to form a group of W cards starting from that card.
- If a group of W cards is formed, we decrement the frequency of all those cards in the hash map. We also remove them from the priority queue if their frequency becomes zero.
- If we are unable to form a group of W cards starting from the smallest card, we return false.
- We repeat steps 3-5 until all cards have been processed.
- If we are able to form groups of W cards for all cards, we return true.

Here is the implementation of the above steps in Python:

class Solution:

def isNStraightHand(self, hand: List[int], W: int) -> bool:

# Count frequency of each card

freq = collections.Counter(hand)

```
# Initialize a priority queue with the keys of the frequency map
pq = queue.PriorityQueue()
for key in freq:
pq.put(key)
# Process cards in ascending order of value
while not pq.empty():
start = pq.get()
for i in range(W-1):
next_card = start + i + 1
if next_card not in freq:
return False
if freq[next_card] == 0:
return False
freq[next_card] -= 1
if freq[next_card] == 0:
del freq[next_card]
# All cards have been processed
return True
```

The time complexity of this solution is O(n log n) because we are using a priority queue for processing the cards. The space complexity is O(n) because we are using a hash map to store the frequency of each card.

## Step by Step Implementation For Hand Of Straights

/** * @author: * @date: * @description: */ class Solution { public boolean isNStraightHand(int[] hand, int W) { } }

def isNStraightHand(hand, W): # check if the length of the hand is a multiple of W if len(hand) % W != 0: return False # sort the hand in ascending order hand.sort() # keep track of the number of straights we have found num_straights = 0 # start with the first card in the hand i = 0 # while we haven't reached the end of the hand while i < len(hand): # find the end of the current straight j = i + W # check if the current straight is valid if isValidStraight(hand[i:j]): # if so, increment the number of straights num_straights += 1 # and move on to the next straight i = j else: # otherwise, move on to the next card i += 1 # return whether or not we found all of the straights return num_straights == len(hand) // W def isValidStraight(cards): # keep track of the previous card prev_card = None # for each card in the straight for card in cards: # if we have seen a previous card if prev_card is not None: # check if the current card is exactly one higher than the previous card if card != prev_card + 1: return False # update the previous card prev_card = card # if we get here, the straight is valid return True

/** * @param {number[]} hand * @param {number} W * @return {boolean} */ var isNStraightHand = function(hand, W) { // if the length of the hand is not a multiple of W, then it's not possible to have a straight if (hand.length % W !== 0) { return false; } // sort the hand hand.sort((a, b) => a - b); // create a map to store the counts of each card const map = {}; for (let i = 0; i < hand.length; i++) { if (!map[hand[i]]) { map[hand[i]] = 1; } else { map[hand[i]]++; } } // iterate through the map, for each card check if there are enough subsequent cards to form a straight let i = 0; while (i < hand.length) { const card = hand[i]; // if this card doesn't exist in the map, or there aren't enough cards to form a straight, return false if (!map[card] || map[card] === 0 || (W - map[card]) > (hand.length - i)) { return false; } // otherwise, decrement the count of this card and all subsequent cards by the number needed to form a straight for (let j = 0; j < W; j++) { map[card + j] -= map[card]; } // move on to the next card i++; } return true; };

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { // An empty tree is BST if (root == NULL) return true; // Do Inorder traversal and check if the prev node is // smaller than the current node stackst; TreeNode *curr = root; TreeNode *prev = NULL; while (curr != NULL || !st.empty()) { /* Reach the left most TreeNode of the curr TreeNode */ while (curr != NULL) { st.push(curr); curr = curr->left; } /* Current must be NULL at this point */ curr = st.top(); /* Make sure current TreeNode's value is not smaller than the previous TreeNode's value */ if (prev != NULL && prev->val >= curr->val) return false; /* Update prev TreeNode */ prev = curr; /* Move to the right */ curr = curr->right; /* Remove the TreeNode at the top of the stack, do the same thing as TreeNode->right = TreeNode->right->left */ st.pop(); } /* If we reach here means the tree is BST */ return true; } };

using System; public class Solution { public bool IsNStraightHand(int[] hand, int W) { //check for edge cases if (hand.Length % W != 0) { return false; } if (W == 1) { return true; } //sort the array Array.Sort(hand); //keep track of the number of cards needed for each value int[] numsLeft = new int[W]; //go through the array and update the number of cards needed for each value for (int i = 0; i < hand.Length; i++) { //if we don't need any more cards of this value, continue if (numsLeft[hand[i] % W] == 0) { continue; } //decrement the number of cards needed of this value and all values before it for (int j = 0; j <= hand[i] % W; j++) { //if we need more cards of this value than we have, return false if (numsLeft[j] < 0) { return false; } numsLeft[j]--; } } //if we get to this point, we have the correct number of cards for each value return true; } }