846. Hand of Straights (medium)

Hand of Straights is a Medium level 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]

DISCUSSION:

The first insight into this problem is related to groupSize and has two parts: 

• groupSize of 1 should always return True since groups of 1 are always straights.
• groupSize must divide the hand length. In other words: len(hand)%groupSize == 0. If group size does not divide handLength then the hand can clearly not be rearranged into groupSize groups.

The second insight into this problem is related to my solution strategy, which is that each group should start with the smallest card that is still in the hand. That is, if a hand is [1, 2, 6, 7] and groupSize 2 then the first group starts with 1 and the second group starts with 6.

My solution sorts the hand, then for each group of groupSize: 

• pop the first (smallest) element off the list
• Find the index of value first+1 in the list
• If that index is found, pop it off the list
• If the index is not found, return False since this group cannot be completed.

If this process terminates with an empty hand then return True.

Returning False is handled inside of the loop.

Runtime: 236 ms. Beats 19.10% of users

Memory: 17.93 MB. Beats 97.23% of users.

class Solution:

def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:

# SOLUTION:

# Insight 1: groupSize MUST divide the length of hand.

# If it does not, return False

#

# Insight 2: Every time you make a group, the lowest

# card still in the hand must be the start of the group

if len(hand) % groupSize != 0:

return False

# Group size of 1 is always popssible

if groupSize == 1:

return True

# Sort the hand

hand.sort()

# Group-ify it until the hand is empty or you fail

while len(hand) >= groupSize:

curVal = hand.pop(0)

for i in range(groupSize-1):

# Look for the next card needed for this group

# Its value is curVal + 1.

try:

nextElemIdx = hand.index(curVal + 1)

except ValueError:

# If the next card was not found, then we

# cannot make a group

return False

curVal = hand.pop(nextElemIdx)

return True