LC846. Hand of Straights

Approach 1: Min Heap + Counter

from collections import Counter
from heapq import heappush, heappop
 
class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        counts = Counter(hand)
        
        minHeap = list(counts.keys())
        heapify(minHeap)
 
        while minHeap:
            firstItem = minHeap[0]
 
            for item in range(firstItem, firstItem + groupSize):
                if item not in counts:
                    return False
                
                counts[item] -= 1
 
                if counts[item] == 0:
                    # If min item in heap is not the same as current item,
                    # the next group will have a hole and thus won't be having
                    # consecutive elements. So, bail.
                    if item != minHeap[0]:
                        return False
 
                    heappop(minHeap)
        
        return True

Complexity

Time: $O(n\cdot log(n))$
Space: $O(n)$

Approach 2: Sorting + Counter

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0: return False
 
        uniqueCards = list(sorted(set(hand)))
        counts = Counter(hand)
        minCard, maxCard = min(uniqueCards), max(uniqueCards)
 
        i = 0
        while i < len(uniqueCards):
            if i + groupSize > len(uniqueCards):
                return False
 
            startIndex, startItem = i, uniqueCards[i]
            for offset in range(0, groupSize):
                curr = startItem + offset
                j = startIndex + offset
 
                if counts[curr] == 0:
                    return False
 
                counts[curr] -= 1
 
                if counts[uniqueCards[i]] == 0 and counts[curr] > 0:
                    i = j
                
                # Optimization: there is no point if the next group starts with
                # one of the earlier elements from current group and then there
                # is a "hole" after this element—the new group cannot be formed
                # since elements must be consecutive.
                if counts[uniqueCards[i]] > 0 and counts[curr] == 0:
                    return False
            
            if counts[uniqueCards[i]] == 0:
                i += groupSize
        
        return True

Complexity

Time: $O(n\cdot log(n))$
Space: $O(n)$

Other Languages

Swift

import Collections
 
class Solution {
    func isNStraightHand(_ hand: [Int], _ groupSize: Int) -> Bool {
        var counts: [Int:Int] = [:]
        for card in hand {
            counts[card, default: 0] += 1
        }
 
        var minHeap = Heap(counts.keys)
 
        while !minHeap.isEmpty {
            let firstItem = minHeap.min!
 
            for item in firstItem..<(firstItem + groupSize) {
                guard let _ = counts[item] else {
                    return false
                }
 
                counts[item]! -= 1
 
                if counts[item] == 0 {
                    if item != minHeap.min {
                        return false
                    }
 
                    minHeap.popMin()
                }
            }
        }
 
        return true
    }
}

Notes

See Swift Collections documentation on Heap.