LC1296. Divide Array in Sets of K Consecutive Numbers

NOTE

This problem is same as LC846. Hand of Straights

Approach 1: Heap + Counter

from collections import Counter
from heapq import heapify, heappop
 
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counts = Counter(nums)
        minHeap = list(counts.keys())
        heapify(minHeap)
 
        while minHeap:
            firstItem = minHeap[0]
 
            for item in range(firstItem, firstItem + k):
                if item not in counts:
                    return False
                
                counts[item] -= 1
 
                if counts[item] == 0:
                    if item != minHeap[0]:
                        return False
                    
                    heappop(minHeap)
        
        return True

Complexity

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