846. Hand of Straights

Problem

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

Constraints:

• 1 <= hand.length <= 10000
• 0 <= hand[i] <= 1000000000
• 1 <= groupSize <= hand.length

Main Idea

Alice has a hand of cards, and she wants to rearrange these cards into several groups, so that each group has groupSize cards and consists of groupSize consecutive cards.

You are given an integer array hand where hand[i] is written on the ith card, and an integer groupSize. If she can rearrange these cards, return true; otherwise, return false.

Solution Approach

Greedy algorithm

• Sort hand in ascending order
• Perform hash counting on the numbers in hand (key: number, value: count)
• Traverse the numbers in hand; use numbers with a count greater than 1 as the start of a straight, and look for the subsequent elements of the straight. If a complete straight cannot be found, return false
• If all numbers can form complete straights, return true

##Code

package leetcode

import "sort"

func isNStraightHand(hand []int, groupSize int) bool {
	mp := make(map[int]int)
	for _, v := range hand {
		mp[v] += 1
	}
	sort.Ints(hand)
	for _, num := range hand {
		if mp[num] == 0 {
			continue
		}
		for diff := 0; diff < groupSize; diff++ {
			if mp[num+diff] == 0 {
				return false
			}
			mp[num+diff] -= 1
		}
	}
	return true
}