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.
bool isNStraightHand(vector<int>& hand, int W) {
unordered_map<int, int> count;
for (int num : hand) {
count[num]++;
}
while (!count.empty()) {
int min = INT_MAX;
for (auto& it : count) {
min = min < it.first ? min : it.first;
}
for (int i = 0;
i < W;
i++) {
if (count.find(min + i) == count.end()) {
return false;
}
count[min + i]--;
if (count[min + i] == 0) {
count.erase(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?
