Untitled

# O(nlogn) greedy solution: sort and then attempt to build hands using the smallest cards first
# The intuition here is that for each card value x in increasing order, the only other cards in a straight that starts
# with x are the (groupSize - 1) next values
# This continues with each value until we reach the end
# Processing them in this order, we can skip missing values that have already been placed in previous hands
# 
# The optimal greedy solution is O(n) time:
# A key intuition is that we don't actually have to sort the list and start with the smallest values first
# We can process each card in order, and just check that we have enough cards to make a straight with this card
# But we have to be careful to make sure that the cards we pick are the optimal ones (explained later)
#
# So first count the number of each card we have
# Then we do the following for each card x:
# 1. Find the lowest possible card y < x. 
#    This is the smallest value < x where counter[y] > 0 (aka we still have a copy of y)
# 2. The range [y, x] contains possible starting values for hands
#    We need to consider all of these values because card x may be part of multiple hands
#    But in order to safely process x and move on, we need to figure out which hands it's part of and remove those
#    from later consideration
#    This means we need process ALL hands that start at a value <= x in increasing order (which is why we find y in step 1)
#    We need to do this because each of these hands may consume cards that impact whether or not we can build a hand with x
#    Note that this is basically what the sorting solution does above, but this process is applied to each card value in a vacuum
#    If at any point we start a hand and can't finish it, return False
# 3. Return True if we can process all cards
# 
# Time complexity is tricky for this one but:
# 1. There are at most groupSize checks per card
# 2. The nested for loops are deceiving at first glance: we only process each value once
# So the overall time complexity is O(n)
# Note that in practice, even though O(n) < O(nlogn), all the extra processing will likely make this solution slower than the sorting one
#
# Both solutions are O(n) space

# The sorting solution
class Solution2:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # check that we have enough cards:
        if len(hand) % groupSize:
            return False

        hand.sort()
        counts = Counter(hand)
        for card in hand:
            # check if we already used all copies of this card in prior hands
            # since this is just starting a new hand, it's fine to skip it
            if not counts[card]:
                continue

            # this is an optimization, since we can actually build multiple hands with the same 
            # starting value at the same time
            card_count = counts[card]

            # start building a straight using this card as the min value
            for i in range(card, card + groupSize):
                if counts[i] < card_count:
                    # we're missing a card required for the current straight
                    return False
                counts[i] -= card_count
            
        return True

# Optimal solution
class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # check that we have enough cards:
        if len(hand) % groupSize:
            return False

        counts = Counter(hand)
        for card in hand:
            # find the starting card for a straight sequence
            # at each step, check if we still have a copy of the next lowest card
            overall_start = card
            while counts[overall_start - 1]:
                overall_start -= 1
            
            # build as many straights as we can, using each value from starting_card -> card as the start of a new hand
            # keep in mind that we need at exactly groupSize cards per hand
            for start_card in range(overall_start, card + 1):
                # check if we already used all copies of this card in prior hands
                # since this is just starting a new hand, it's fine to skip it
                if not counts[start_card]:
                    continue

                # this is an optimization, since we can actually build multiple hands with the same 
                # starting value at the same time
                card_count = counts[start_card]

                # build the straight in reverse order, checking that enough copies of the next lowest value exist
                # if not, building the hand starting at `c` is impossible
                for other_card in range(start_card + groupSize - 1, start_card - 1, -1):
                    # we need at least the same number of copies of each other_card in the straight
                    if counts[other_card] < card_count:
                        return False

                    counts[other_card] -= card_count
            
        return True