Hand of Straights
Alice has a hand of cards, given as an array of integers. For some integer W, if all the cards in her hand are exactly W consecutive integers, then it is said that her hand is "straight". For example, [1,2,3,4,5] and [5,6,7,8,9] are both straight hands. However, [1,2,3,4,6] is not a straight hand. Given an integer array hand of integers and an integer W, return true if Alice's hand is straight, false otherwise.
Constraints:
- 1 <= hand.length <= 1000
- 0 <= hand[i] <= 10000
- 1 <= W <= 10000
Examples:
Input: [1,2,3,6,2,3,4,7,8]
Output: true
Explanation: We can form two straight hands: [1,2,3] and [6,7,8]
Solutions
Hash Table
We use a hash table to count the frequency of each number in the hand. Then we try to form straight hands by removing W consecutive numbers from the hash table. If we can remove all numbers, then the hand is straight.
function isNStraightHand(hand, W) {
let count = new Map();
for (let num of hand) {
count.set(num, (count.get(num) || 0) + 1);
}
while (count.size > 0) {
let min = Math.min(...count.keys());
for (let i = 0; i < W; i++) {
if (!count.has(min + i)) {
return false;
} else {
count.set(min + i, count.get(min + i) - 1);
if (count.get(min + i) === 0) {
count.delete(min + i);
}
}
}
}
return true;
}
Follow-up:
What if the hand is not necessarily straight, but we want to find the longest straight hand that can be formed?
