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
stack st;
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;
}
}