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.
def isNStraightHand(hand, W):
count = {} for num in hand:
count[num] = count.get(num, 0) + 1 while count:
min_num = min(count.keys()) for i in range(W):
if min_num + i not in count:
return False count[min_num + i] -= 1 if count[min_num + i] == 0:
del count[min_num + i] return TrueFollow-up:
What if the hand is not necessarily straight, but we want to find the longest straight hand that can be formed?
