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.
public boolean isNStraightHand(int[] hand, int W) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : hand) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
while (!count.isEmpty()) {
int min = Collections.min(count.keySet());
for (int i = 0;
i < W;
i++) {
if (!count.containsKey(min + i)) {
return false;
}
count.put(min + i, count.get(min + i) - 1);
if (count.get(min + i) == 0) {
count.remove(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?
