Hand of Straights
MediumThe problem
hand holds the numbers written on your cards. Return true if you can split all the cards into groups of exactly groupSize cards each, where the numbers in a group are consecutive (like 4, 5, 6). Otherwise return false.
- Example 1Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3Output: true
Groups [1, 2, 3], [2, 3, 4] and [6, 7, 8] use every card.
- Example 2Input: hand = [1, 2, 3, 4, 5], groupSize = 4Output: false
There are 5 cards, which cannot be split into groups of 4.
- 1 ≤ len(hand) ≤ 10,000
- 0 ≤ hand[i] ≤ 1,000,000,000
- 1 ≤ groupSize ≤ len(hand)
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The smallest remaining card must start a group. Why?
The idea
Count cards; repeatedly take the smallest card with a positive count and decrement the next groupSize−1 consecutive values (fail if one is missing). A min-heap or sorted keys finds the smallest.
Target: O(n log n) time
Go function shape
func isNStraightHand(hand []int, groupSize int) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsNStraightHand: the smallest remaining card can only start a group (nothing smaller is left to precede it),
// so repeatedly start a run at the smallest card and take groupSize consecutive values.
func IsNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
count := map[int]int{}
for _, c := range hand {
count[c]++
}
keys := make([]int, 0, len(count))
for c := range count {
keys = append(keys, c)
}
sort.Ints(keys)
for _, start := range keys {
n := count[start]
if n == 0 {
continue
}
for v := start; v < start+groupSize; v++ {
if count[v] < n {
return false // the run cannot be completed
}
count[v] -= n // start n groups at once
}
}
return true
}