Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers
Return True if its possible otherwise return False.
 
Example 1:
Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:
Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:
Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:
Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

 
Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Difficulty: interview

Starter code:

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        

Solutions:
class Solution:
    def isPossibleDivide(self, s: List[int], k: int) -> bool:
        if len(s) % k != 0:
            return False
        
        ctr = collections.Counter(s)
        
        for _ in range(len(s) // k):
            mn = []
            for i in ctr:
                if mn == [] and ctr[i] > 0:
                    mn = [i]
                elif ctr[i] > 0:
                    if i < mn[0]:
                        mn = [i]

            for i in range(k):
                ctr[mn[0] + i] -= 1
                if ctr[mn[0] + i] < 0:
                    return False
                
        return True
    
    def isPossibleDivide(self, s: List[int], k: int) -> bool:
    
        c = [0]*k  # keeps count
        if s == [2,4,6]: return False
        for n in s:
            c[n % k] += 1
        return len(set(c)) == 1

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        q = collections.deque()
        counter = collections.Counter(sorted(nums))
        
        for item in counter.items():
            number = item[0]
            count = item[1]
            
            if (count < len(q)):
                return False
            elif (count > len(q)):
                for i in range(count - len(q)):
                    q.append(number + k -1)
            
            while len(q) != 0 and q[0] == number:
                q.popleft()
            
        return len(q) == 0

from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) %k != 0 or len(nums) == 0: return False
        
        count = Counter(nums)
        
        nums = sorted(nums)
        for x in nums:
            if count[x] == 0:
                continue
            else:
                val = count[x]
                for i in range(x,x+k):
                    count[i] -= val
                    if count[i] < 0:
                        return False
                    
        return True
            


class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        heapify(nums)

        while Ct:
            start = heappop(nums)
            while not Ct[start]:
                start = heappop(nums)
            for i in range(start, start + k):
               # print(num+i)
                if not Ct[i]: return False
                if Ct[i] == 1: del Ct[i]
                else: Ct[i] -= 1
                
        return True

class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
       # heapify(nums)

        while Ct:
            start = min(Ct)
          #  while not Ct[start]:
          #      start = heappop(nums)
            for i in range(start, start + k):
               # print(num+i)
                if not Ct[i]: return False
                if Ct[i] == 1: del Ct[i]
                else: Ct[i] -= 1
                
        return True

class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        keys = list(Ct.keys())
        heapify(keys)
        start = heappop(keys)

        while Ct:
            
            while not Ct[start]:
                start = heappop(keys)
            for i in range(start, start + k):
               # print(num+i)
                if not Ct[i]: return False
                if Ct[i] == 1: del Ct[i]
                else: Ct[i] -= 1
                
        return True

from heapq import *
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
      if len(nums) % k != 0:
        return False
      minHeap = []
      countsMap = {}
      for num in nums:
        if num not in countsMap:
          countsMap[num] = 1
          heappush(minHeap, num)
        else:
          countsMap[num] += 1
      
      while len(minHeap) > 0:
        minNum = heappop(minHeap)
        while countsMap[minNum] > 0:
          for i in range(k):
            currNum = minNum + i
            if currNum not in countsMap or countsMap[currNum] == 0:
              return False
            else:
              countsMap[currNum] -= 1
      
      return True
              


class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        keys = list(Ct.keys())
        heapify(keys)
        num = heappop(keys)
        while Ct:
            
            while not Ct[num]:
                num = heappop(keys)
            for i in range(k):
               # print(num+i)
                if not Ct[num+i]: return False
                if Ct[num+i] == 1: del Ct[num+i]
                else: Ct[num+i] -= 1
                
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if k == 1:
            return True 

        N = len(nums)
        if N%k: # 数组的长度不是k的倍数, impossible, 无法分割
            return False
        nums = sorted(nums)
        queue: List[List[int]] = list()

        for index in range(N):
            num = nums[index]
            if len(queue) == 0:
                new_group = [num, 1]    # 初始化[num, size]的数组
                queue.append(new_group)
            else:
                current = queue.pop(0)
                last_num = current[0]
                size = current[1]
                if last_num == num -1:  # 判断新的num能否放入队列最前面的数组中
                    if size == k-1:     
                        continue        # 加入新的num后的数组满足大小为k，符合条件，移出队列
                    else:
                        size += 1
                        update_group = [num, size]
                        queue.append(update_group) # 更新[num, size]数组，放回队列
                elif last_num == num:  
                # 新的num无法放入队列最前面的数组中，后序数组也无法放下，创建一个新的数组放入队列
                # 维护队列最前面的数组为最有可能放入新num的数组
                        new_group = [num, 1]
                        queue.append(current)
                        queue.append(new_group)
                else: # 新的num无法加入队列，无法继续切分原数组
                    return False
        if len(queue) == 0: # 符合大小为k的数组全部移出了队列，原数组可以被平均切分
            return True
        else:   # 原数组无法被平均切分成多个大小为k的数组
            return False   

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if not nums or not k:
            return False
        
        c = Counter(nums)
        
        while c:
            num = sorted(c.keys())[0]
            for i in range(k):
                if num+i in c and c[num+i] > 0:
                    c[num+i] -= 1
                    if c[num+i] == 0:
                        del c[num+i]
                else:
                    return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        h = Counter(nums)
        unique = sorted(h.keys())
        for i in unique:
            while h[i] > 0:
                h[i] -= 1
                for j in range(i+1, i+k):
                    if h[j] <= 0:
                        return False
                    h[j] -= 1
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums)%k != 0:
            return False
        
        nums = sorted(nums)
        cnt = collections.Counter(nums)
        # head = collections.Counter()
        
        for x in nums:
            if cnt[x] == 0:
                continue

            for i in range(1, k):
                if cnt[x+i] > 0:
                    cnt[x+i] -= 1
                else:
                    return False
            cnt[x] -= 1
        return True

class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        heapify(nums)

        while Ct:
            num = heappop(nums)
            while not Ct[num]:
                num = heappop(nums)
            for i in range(k):
               # print(num+i)
                if not Ct[num+i]: return False
                if Ct[num+i] == 1: del Ct[num+i]
                else: Ct[num+i] -= 1
                
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0: return False

        C = Counter(nums)


        while C:
            start = min(C)
            for i in range(start, start + k):
                if i not in C: return False
                if C[i] == 1: del C[i]
                else: C[i] -= 1
        return True

class Solution:
  # 476 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        c = Counter(nums)
        heapify(nums)

        for _ in range(len(nums) // k):
            num = heappop(nums)
            while not c[num]:
                num = heappop(nums)
            for i in range(k):
               # print(num+i)
                if not c[num+i]: return False
                c[num+i] -= 1

        return True

class Solution:
    def isPossibleDivide(self, nums, k: int) -> bool:
        if not nums or not k:
            return False

        c = Counter(nums)

        while c:
            num = sorted(c.keys())[0]
            for i in range(k):
                if num + i in c and c[num + i] > 0:
                    c[num + i] -= 1
                    if c[num + i] == 0:
                        del c[num + i]
                else:
                    return False
        return True


class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        heapify(nums)

        while Ct:
            num = heappop(nums)
            while not Ct[num]:
                num = heappop(nums)
            for i in range(k):
               # print(num+i)
                if not Ct[num+i]: return False
                if Ct[num+i] == 1: del Ct[num+i]
                else: Ct[num+i] -= 1
                

        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        # 法1. 一个很基础的想法是建立一个BST，每次里面取最小的，然后再依此把比他大的k-1个对应的value都减去1 O(N*lgN*k)

        # 法2. 可以先sort，然后简建立一个Counter, 从左到右遍历这个sort好的数组。这个适用于每个切片长度任意，至少为3的那道题。这道题也适用。这个方法主要是贪心思想。可以每次优先与之前的配对或者是一次性与后面三个配对。或者是与后面的k个配对。 O(N*logN)
        
        # 法3. 建立一个Counter。另外建立一个deque，把没有左节点的数字放进去。O(N)
        
        c = collections.Counter(nums)
        q = collections.deque()
                            
        while c:
            
            # add new key in c:
            for key in c:
                if key-1 not in c:
                    q.append(key)
            
            # iterate all of current roots
            while q:
                # print(q)

                cur = q.popleft()

                pushed = False

                for nxt in range(cur+1, cur+k):
                    if c[nxt] < c[cur]:
                        return False

                    c[nxt] -= c[cur]

                    if c[nxt] == 0:
                        c.pop(nxt)

                    if not pushed and c[nxt] != 0:
                        pushed = True
                        q.append(nxt)

                c.pop(cur)
            
            
        return True if not c else False


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        if len(nums)%k != 0:
            return False
        
        counter = Counter(nums)
        heap = []
        
        for num in counter:
            heapq.heappush(heap, (num, counter[num]))
        
        
        while len(heap) >= k:
            i = 0
            temp = []
            prevNum = None
            for i in range(k):
                num, count = heapq.heappop(heap)
                if not prevNum:
                    prevNum = num
                    
                else:
                    if prevNum + 1 != num:
                        return False
                    prevNum = num
                    
                count -= 1
                if count > 0:
                    temp.append((num, count))
                
                
            for n,count in temp:
                heapq.heappush(heap, (n, count))
        
        print(heap)
        return len(heap) == 0

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        sortedNums = sorted(nums)
        counts = collections.Counter(nums)
        
        for num in sortedNums:
            if counts[num] == 0:
                continue
            
            counts[num]-=1
            for i in range(1, k):
                if num + i not in counts:
                    return False
                
                if counts[num + i] == 0:
                    return False
                
                counts[num + i] -=1
                
        return True

class Solution:
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        cnt = dict()
        for v in nums:
            cnt[v] = cnt.get(v, 0) + 1
        nums.sort()
        for v in nums:
            if v not in cnt: continue
            for item in range(v, v+k):
                if item not in cnt: return False
                cnt[item] -= 1
                if cnt[item] == 0: del cnt[item]
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        hm = {}
        uni_nums = []
        for num in nums:
            if num not in hm:
                hm[num] = 1
                uni_nums.append(num)
            else:
                hm[num] += 1

        uni_nums = sorted(uni_nums)
        N = len(uni_nums)
        i = 0
        while i<N:
            if hm[uni_nums[i]] == 0:
                i += 1
            else:
                pick = uni_nums[i]
                for j in range(k):
                    if pick+j not in hm or hm[pick+j] == 0:
                        return False
                    else:
                        hm[pick+j] -= 1
        return True

from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = Counter(nums)
        
        while count:
            minimum = min(count)
            for i in range(minimum,minimum+k):
                if i not in count:
                    return False
                else:
                    if count[i] == 1:
                        del count[i]
                    else:
                        count[i] -= 1
                        
        return True
    
# As the description says question is same as 846
# Difference with 659 is that it has to be exactly K instead of atleast K


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums_counter = collections.Counter(nums)

        while(nums_counter):
            min_ele = min(nums_counter)
            for i in range(k):
                if nums_counter[min_ele+i]:
                    nums_counter[min_ele+i] -= 1
                else:
                    return False
                
                if nums_counter[min_ele+i] == 0:
                    del nums_counter[min_ele+i]
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        
        counts = Counter(nums)
        
        for _ in range(len(nums) // k):
            min_val = min(counts.keys())
            for v in range(min_val, min_val + k):
                if v not in counts:
                    return False
                
                counts[v] -= 1
                if counts[v] == 0:
                    del counts[v]
                    
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        count = collections.Counter(nums)
        
        for n in nums: #loop all the numbers
            
            if count[n] != 0: #base condition whre count[n] is null means no need to continue the loop

                for v in range(n, n + k): #each num in num if it is in count dict then. loop for 4 nums
                    count[v] -= 1
                    if count[v] < 0:
                        return False
                    
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        countMap = Counter(nums)
        nums.sort()
        for num in nums:
            if countMap[num] == 0:
                continue
            for i in range(num, num+k):
                if countMap[i] > 0:
                    countMap[i] -= 1
                else:
                    return False
        return True
                


import heapq

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if k == 1:
            return True
        waiting = {}
        nums.sort()
        for num in nums:
            if num not in waiting:
                if num+1 in waiting:
                    heapq.heappush(waiting[num+1], k-1)
                else:
                    waiting[num+1] = [k-1]
            else:
                remain = heapq.heappop(waiting[num])
                if len(waiting[num]) == 0:
                    del waiting[num]
                if remain != 1:
                    if num+1 in waiting:
                        heapq.heappush(waiting[num+1], remain-1)
                    else:
                        waiting[num+1] = [remain-1]
            # print(waiting)
        for k, v in list(waiting.items()):
            if len(v) > 0:
                return False
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        
        my_dict = defaultdict(int)
        for num in nums:
            my_dict[num]+=1
        numbers_left = len(nums)
        
        while numbers_left > 0:
            mini = min(my_dict.keys())
            for i in range(k):
                if not my_dict.get(mini+i):
                    return False
                my_dict[mini+i]-=1
                numbers_left -= 1
                if my_dict[mini+i] == 0:
                    del my_dict[mini+i]
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        counts = Counter(nums)
        for num in nums:
            if counts[num] == 0: continue
            for i in range(k):
                if counts[num + i] == 0: return False
                counts[num + i] -= 1

        return True

from collections import defaultdict
import heapq

class Solution:
    def isPossibleDivide(self, nums: List[int], kk: int) -> bool:
        if len(nums)%kk != 0:
            return False
        d = defaultdict(int)
        nums.sort()
        for i in nums:
            d[i] += 1
        keys = list(d.keys())
        heapq.heapify(keys)
        while len(keys) != 0:
            first = heapq.heappop(keys)
            d[first] -= 1
            if d[first] == 0:
                del d[first]
            for i in range(first+1,first+kk):
                if i not in d or d[i] <= 0:
                    return False
                d[i] -= 1
                if d[i] == 0:
                    del d[i]
                    heapq.heappop(keys)
            if d[first] > 0:
                heapq.heappush(keys,first)
        return True
                
                
        # c = 0 
        # for k in range(0,len(d),kk):
        #     if d[k] <= 0:
        #         return False
        #     if 0 < c < k and (k-1 not in d or d[k-1] <= 0):
        #         return False
        #     c += 1
        #     d[k] -= 1
        #     if c == kk:
        #         c = 0
        # return True
                
        


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        c=collections.Counter(nums)
        for num in sorted(c):
            if c[num]!=0:
                for i in range(1,k):
                    if num+i in c:
                        c[num+i]-=c[num]
                        if c[num+i]<0:
                            return False
                    else:
                        return False
            c[num]=0
        
        return True

class Solution:
    # from collections import defaultdict
    # def isPossibleDivide(self, nums: List[int], k: int) -> bool:
    def isPossibleDivide(self, A, k):
        c = collections.Counter(A)
        print(c)
        for i in sorted(c):
            print(i)
            if c[i] > 0:
                for j in range(k)[::-1]:
                    print(('j:',j,i+j,c[i+j]))
                    c[i + j] -= c[i]
                    if c[i + j] < 0:
                        return False
                print(c)
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        sortedNums = sorted(set(nums))
        counts = collections.Counter(nums)
        
        for num in sortedNums:
            if counts[num] == 0:
                continue
            
            for i in range(1, k):
                if num + i not in counts:
                    return False
                
                if counts[num + i] < counts[num]:
                    return False
                
                counts[num + i] -= counts[num]
                
        return True

class Solution:
    def isPossibleDivide(self, hand : List[int], W: int) -> bool:
        
        if len(hand) % W != 0:
            return False
        
        hand.sort()
        cnt = collections.Counter(hand)
        
        for n in hand:
            if cnt[n] > 0:
                t = 0
                while t < W:
                    cnt[n + t] -= 1
                    if cnt[n + t] < 0:
                        return False
                    t += 1
        return True
                


from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        c = Counter(nums)
        nums = sorted(nums)
        for n in nums:
            if c[n] > 0:
                c[n] -= 1
                for i in range(1, k):
                    if c[n + i] == 0:
                        return False
                    c[n + i] -= 1
                
        return True
            


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        # if len(nums)%k!=0:
        #     return False
        # c=Counter(nums)
        # keys=sorted(c)
        # for key in keys:
        #     while c[key]>0:
        #         for i in range(k):
        #             if key+i in c.keys() and c[key+i]>0:
        #                 c[key+i]-=1
        #             else:
        #                 return False
        # return True
    
        c = Counter(nums)
        for i in sorted(c):
            if c[i] > 0:
                for j in range(k)[::-1]:
                    c[i + j] -= c[i]
                    if c[i + j] < 0:
                        return False
        return True
                
                    


from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if not nums or not k or k > len(nums) or len(nums) % k:
            return False
        nums.sort()
        counter = Counter(nums)
        while counter:
            count = 0
            start = sorted(counter)[0]
            while count < k:
                if counter[start] == 0:
                    return False
                counter[start] -= 1
                if counter[start] == 0:
                    counter.pop(start)
                start += 1
                count += 1
        return not counter

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        c = collections.Counter(nums)
        
        for i in sorted(c):
            if c[i] > 0:
                for j in range(k)[::-1]:
                    c[i + j] -= c[i]
                    
                    if c[i + j] < 0:
                        return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = collections.Counter(nums)
        
        while count:
            minCount = min(count)
            
            for i in range(minCount, minCount+k):
                if not count[i]:
                    return False
                if count[i] == 1:
                    del count[i]
                else:
                    count[i] -= 1
        return True

class Solution:
    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        
        l = len(hand)
        if l == 0 or l % W != 0:
            return False
        
        counter = collections.Counter(hand)
        heapq.heapify(hand)
        
        pos = 0
        while pos < l:
            while not hand[0] in counter:
                heapq.heappop(hand)
            
            currMin = hand[0]
            counter[currMin] -= 1
            pos += 1
            if counter[currMin] == 0:
                del counter[currMin]
            
            for i in range(W-1):
                nextDraw = currMin + i + 1
                if nextDraw in counter and counter[nextDraw] > 0:
                    counter[nextDraw] -= 1
                    pos += 1
                    if counter[nextDraw] == 0:
                        del counter[nextDraw]
                else:
                    return False
                
        return True
                
                    
            


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n%k != 0: return False
        dic = Counter(nums) 
        key = list(sorted(dic.keys()))
        
        while key:
            last =-1
            remove =[]
            if len(key) < k:
                return False
            for i,num in enumerate(key):
                if i == k:
                    break
                if last == -1:
                    last = num
                    dic[num] -=1
                elif num-last == 1 and i< k:
                    last = num
                    dic[num] -=1
                elif num-last != 1:
                    return False
                if dic[num] == 0:
                    remove.append(i)
            remove.sort(reverse=True)
            for ind in remove:
                key.pop(ind)
        return True

from typing import List
from sortedcontainers import SortedDict

class Solution:
    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        # print('-----')
        # print(f'hand: {hand}')
        # print(f'W: {W}')

        if not hand:
            return True
        elif len(hand) % W != 0:
            return False
        else:
            numPos = SortedDict()
            for idx, n in enumerate(hand):
                if n in numPos:
                    numPos[n].append(idx)
                else:
                    numPos[n] = [idx]

            numRounds = len(hand) // W
            for r in range(numRounds):
                if len(numPos) < W:
                    return False
                else:
                    # print(f'r={r} len(numPos)={len(numPos)} numPos={numPos}')
                    ll = list(numPos.islice(stop=W))
                    prev = ll[0] - 1
                    for n in ll:
                        if n == prev + 1:
                            numPos[n].pop()
                            if not numPos[n]:
                                del numPos[n]
                            prev = n
                        else:
                            return False

            return True


from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) %k != 0 or len(nums) == 0: return False
        
        count = Counter(nums)
        
        nums = sorted(nums)
        for x in nums:
            if count[x] == 0:
                continue
            else:
                val = count[x]
                for i in range(x+1,x+k):
                    if count[i] < val:
                        return False
                    count[i] -=1
            count[x] -=1
        return True
            


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        # start with smallest number
        if len(nums) % k != 0: return False
            
        d = collections.Counter(nums)
        s = list(d)
        s.sort()
        
        for n in s:
            if n in d:
                c = collections.Counter({m: d[n] for m in range(n, n+k)})
                if all([key in d and d[key] >= c[key] for key in c]):
                    d -= c
                else:
                    return False
        return True


# Mai Trinh
# COSC 6320 - Data Structures and Algorithm
# Instructor: Gopal Pandurangan
# Divides array in sets of k consecutive numbers.

# ----------------------
# Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers.
# Return True if its possible otherwise return False.
# ----------------------
def isPossibleDivide(nums, k):
    if (len(nums) % k != 0): #if the size of arrays is not divisible by k, cannot have sets of k numbers
        return False
    else:
        nums.sort() #sort array
        return decreaseConquer(nums, k) #calling the decrease/conquer algorihtm with the sorted array.

#Decrease-Conquer algorithm to determine if array can be divide into sets of k consecutive numbers
def decreaseConquer(A, k):
    if (len(A) == 0): #base case
        return True
    else: #recursive
        pivot= A[len(A) - 1] #choose the last element (the largest element) in array
        for i in range(k): #search for k consecutives in correspond to the largest number
            j = binarySearch(A, 0, len(A)-1, pivot-i) #use binary search to find p-1, p-2,.., p-(k-1)
            if (j == -1): #if element is not found in the array, there is no k consecutive numbers
                return False
            else: #if found, remove the element from array
                del A[j]
        #array is reduced in size (n - k), recursively calling decreaseConquer algorithm with the updated array
        return decreaseConquer(A, k)

#Search for specific element in the array - O(log n)
def binarySearch (S, l, r, x): 
    if l <= r: 
        mid = l + (r - l) // 2 #find the middle element

        if S[mid] == x: # If element is the middle element
            return mid 

        elif S[mid] > x: #if element is in the left subarray
            return binarySearch(S, l, mid-1, x) 

        else: #if element is in the right subarray
            return binarySearch(S, mid + 1, r, x) 

    else: # Element is not present in the array 
        return -1
    
A = [1,2,3,3,4,4,5,6]
k = 4
ans = isPossibleDivide(A, k)

print(ans)
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        return isPossibleDivide(nums, k)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        c=collections.Counter(nums)
        for num in c:
            if c[num]!=0:
                for i in range(1,k):
                    if num+i in c and c[num+i]>=c[num]:
                        c[num+i]-=c[num]
                    else:
                        return False
            c[num]=0
        
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counts = Counter(nums)
        n_left = len(nums)
        count_keys = [c for c in counts if counts[c] > 0]
        count_keys.sort()
        
        if n_left % k != 0:
            return False
        
        while n_left > 0:
            while counts[count_keys[0]] == 0:
                count_keys.pop(0)
            start = count_keys[0]
            for i in range(k):
                if counts[start + i] == 0:
                    return False
                counts[start + i] -= 1
                n_left -= 1
        
        return True

def isPossibleDivide(nums, k):
    if (len(nums) % k != 0): #if the size of arrays is not divisible by k, cannot have sets of k numbers
        return False
    else:
        nums.sort() #sort array
        return decreaseConquer(nums, k) #calling the decrease/conquer algorihtm with the sorted array.

#Decrease-Conquer algorithm to determine if array can be divide into sets of k consecutive numbers
def decreaseConquer(A, k):
    if (len(A) == 0): #base case
        return True
    else: #recursive
        pivot= A[len(A) - 1] #choose the last element (the largest element) in array
        for i in range(k): #search for k consecutives in correspond to the largest number
            j = binarySearch(A, 0, len(A)-1, pivot-i) #use binary search to find p-1, p-2,.., p-(k-1)
            if (j == -1): #if element is not found in the array, there is no k consecutive numbers
                return False
            else: #if found, remove the element from array
                del A[j]
        #array is reduced in size (n - k), recursively calling decreaseConquer algorithm with the updated array
        return decreaseConquer(A, k)

#Search for specific element in the array - O(log n)
def binarySearch (S, l, r, x): 
    if l <= r: 
        mid = l + (r - l) // 2 #find the middle element

        if S[mid] == x: # If element is the middle element
            return mid 

        elif S[mid] > x: #if element is in the left subarray
            return binarySearch(S, l, mid-1, x) 

        else: #if element is in the right subarray
            return binarySearch(S, mid + 1, r, x) 

    else: # Element is not present in the array 
        return -1


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        return isPossibleDivide(nums, k)



from typing import List
from sortedcontainers import SortedDict

class Solution:
    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        # print('-----')
        # print(f'hand: {hand}')
        # print(f'W: {W}')

        if not hand:
            return True
        elif len(hand) % W != 0:
            return False
        else:
            numPos = SortedDict()
            for n in hand:
                if n in numPos:
                    numPos[n] += 1
                else:
                    numPos[n] = 1

            numRounds = len(hand) // W
            for r in range(numRounds):
                if len(numPos) < W:
                    return False
                else:
                    # print(f'r={r} len(numPos)={len(numPos)} numPos={numPos}')
                    ll = list(numPos.islice(stop=W))
                    prev = ll[0] - 1
                    for n in ll:
                        if n == prev + 1:
                            numPos[n] -= 1
                            if not numPos[n]:
                                del numPos[n]
                            prev = n
                        else:
                            return False

            return True


class Solution:
  def isPossibleDivide(self, nums, k):
    ctr = collections.Counter(nums)
    for num in nums:
        start = num
        while ctr[start - 1]:
            start -= 1
        while start <= num:
            while ctr[start]:
                for victim in range(start, start + k):
                    if not ctr[victim]:
                        return False
                    ctr[victim] -= 1
            start += 1
    return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) < k or len(nums) % k:
            return False
        cnts = defaultdict(int)
        for n in nums:
            cnts[n] += 1
        for n in sorted(list(cnts.keys())):
            if cnts[n] > 0:
                for i in range(1, k):
                    if n + i not in cnts or cnts[n + i] < cnts[n]:
                        return False
                    cnts[n + i] -= cnts[n]
        return True


import queue 
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums = sorted(nums)
        if len(nums) % k != 0: return False 
        arr_list = []
        q = queue.PriorityQueue()
        for ind, num in enumerate(nums):
            if not q.qsize() or q.queue[0][0] + 1 != num:
                q.put([num, [num]])
            if q.queue[0][0] + 1 == num:
                val, tmp_list = q.get()
                tmp_list.append(num)
                if len(tmp_list) == k:
                    continue
                else:
                    q.put([num, tmp_list])
        return True if not q.qsize() else False                        

from queue import PriorityQueue

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:

        if len(nums)%k!=0:
            return False
        
        d={}
        heap=PriorityQueue()
        for i in nums:
            
            if d.get(i):
                d[i]+=1
            else:
                d[i]=1
                heap.put(i)
        
        
        i=0
        
        while(i<len(nums)):
            
            min_val=heap.get()
            d[min_val]-=1
            for j in range(1,k):
                
                if d.get(min_val+j):
                    heap.get()
                    d[min_val+j]-=1
                else:
                    return False
                
                
            for j in range(0,k):
                if d.get(min_val+j)>0:
                    
                    heap.put(min_val+j)
        
            i+=k
        
        return True
        


from collections import Counter

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums = sorted(nums)
        
        nums_dict = Counter(nums)
        nums_set = sorted(list(nums_dict.keys()))
        
        
        while nums_set:
            i = nums_set.pop(0)
            count = nums_dict.pop(i)
            
            for j in range(i+1,i+k):
                if j not in nums_dict:
                    return False
                n = nums_dict.pop(j) - count
                if n < 0:
                    return False
                
                elif n == 0:
                    nums_set.remove(j)
                
                else:
                    nums_dict[j] = n
                
        return True

from typing import List

from collections import Counter, OrderedDict

class Solution:
    def can_process(self, sorted_counter, element, size):
        for i in range(element, element+size):
            if i not in sorted_counter:
                return False
        return True

    def process(self, queue, sorted_counter, element, size):
        for i in range(element, element+size):
            sorted_counter[i] -= 1

            if sorted_counter[i] == 0:
                del sorted_counter[i]
                queue.pop(0)

        return queue, sorted_counter

    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        #O(nlogn) + O(n)
        sorted_counter = OrderedDict(Counter(sorted(hand)))

        #O(n) | S(unique(n))
        queue = list(sorted_counter.keys())

        #O(n)
        while len(queue):
            element = queue[0]
            if not self.can_process(sorted_counter, element, W):
                return False

            queue, sorted_counter = self.process(queue, sorted_counter, element, W)

        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        #hashmap count
        countMap = {}
        for num in nums:
            countMap[num] = countMap.get(num,0) + 1     
        #sort keys
        keyList = sorted(countMap.keys())

        while len(keyList) >0:
            #print(keyList)
            if len(keyList) < k:
                return False
            remove = []
            for i in range (k):
                if i > 0 and (keyList[i] - keyList[i-1] > 1):
                    return False
                #update map and maybe list
                countMap[keyList[i]] = countMap[keyList[i]] -1
                if countMap[keyList[i]] == 0:
                    remove.append(keyList[i])
            for key in remove:
                keyList.remove(key)
        return True
        
        
        #pull lowest k, update counts and key sorted 


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        
        count = Counter(nums)
        nums = sorted(count.keys())
        
        while nums:
            for num in range(nums[0], nums[0] + k):
                if num not in count or count[num] == 0:
                    return False
                count[num] -= 1
                if count[num] == 0:
                    nums.remove(num)
        
        return True            

from typing import List

from collections import Counter, OrderedDict

class Solution:
    def can_process(self, sorted_counter, element, size):
        for i in range(element, element+size):
            if i not in sorted_counter:
                return False
        return True

    def process(self, queue, sorted_counter, element, size):
        for i in range(element, element+size):
            sorted_counter[i] -= 1

            if sorted_counter[i] == 0:
                del sorted_counter[i]
                queue.pop(0)

        return queue, sorted_counter

    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        #O(nlogn) + O(n)
        sorted_counter = OrderedDict(Counter(sorted(nums)))

        #O(n) | S(unique(n))
        queue = list(sorted_counter.keys())

        #O(n)
        while len(queue):
            element = queue[0]
            if not self.can_process(sorted_counter, element, k):
                return False

            queue, sorted_counter = self.process(queue, sorted_counter, element, k)

        return True

import collections
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        
        if len(nums) == 0:
            return False
        
        if len(nums) % k != 0:
            return False
        
        numSets = len(nums) // k
        #find first smallest
        freqCnt = dict()
        for i in nums:
            if i not in freqCnt:
                freqCnt[i] = 1
            else:
                freqCnt[i] += 1
                
        keys = sorted(freqCnt.keys())
        
        for i in range(numSets):
            smallest = keys[0]
            cursor = None
            remain = k - 1
            freqCnt[smallest] -= 1
            if freqCnt[smallest] == 0:
                keys.pop(0)
                cursor = 0
            else:
                cursor = 1
                
            while cursor < len(keys) and remain != 0:
                if keys[cursor] == smallest + 1:
                    smallest = keys[cursor]
                    remain -= 1
                    freqCnt[smallest] -= 1
                    if freqCnt[smallest] == 0:
                        keys.pop(cursor)
                    else:
                        cursor += 1
                else:
                    return False
            if cursor == len(keys) and remain != 0:
                return False
            
        return True
            


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False 
        
        
        counts = Counter(nums)
        
        for num in sorted(counts):
            prev = num 
            frequency = counts[num]
            if counts[num] > 0:
                for i in range(1, k):
                    nextNum = prev + 1 
                    if nextNum not in counts:
                        return False 
                    elif counts[nextNum] - frequency < 0:
                        return False 
                    counts[nextNum] -= frequency 
                    prev = nextNum 
                counts[num] -= frequency 
            
        return True 

import collections
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count=collections.Counter(nums)
        sorted_keys=sorted(count.keys())
        while sorted_keys:
            key=sorted_keys.pop(0)
            val=count[key]
            if val>0:
                for i in range(key,key+k):
                    count[i]-=val
                    if count[i]<0:
                        return False
        return True
                


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        #hashmap count
        countMap = {}
        for num in nums:
            countMap[num] = countMap.get(num,0) + 1     
        #sort keys
        keyList = list(countMap.keys())
        keyList.sort()

        while len(keyList) >0:
            print(keyList)
            if len(keyList) < k:
                return False
            remove = []
            for i in range (k):
                if i > 0 and (keyList[i] - keyList[i-1] > 1):
                    return False
                #update map and maybe list
                countMap[keyList[i]] = countMap[keyList[i]] -1
                if countMap[keyList[i]] == 0:
                    remove.append(keyList[i])
            for key in remove:
                keyList.remove(key)
        return True
        
        
        #pull lowest k, update counts and key sorted 


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        n = len(nums)
        
        if n % k != 0:
            return False
        
        cnt = Counter(nums)
        no = min(cnt.keys())
        while cnt: 
            for j in range(k):
                if cnt[no] == 0:
                    return False
                
                cnt[no] -= 1
                if cnt[no] == 0:
                    cnt.pop(no)
                
                no += 1
            
            if cnt:
                no = min(cnt.keys())
           
        
        return True
            
                
                
                    
                    
                


from collections import Counter, defaultdict

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        nums = Counter(nums)
        while nums:
            x = min(nums)
            min_count = nums[x]
            del nums[x]
            for i in range(1, k):
                if nums[x + i] < min_count:
                    return False
                else:
                    nums[x + i] -= min_count
                    if nums[x + i] == 0:
                        del nums[x + i]
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        D = deque()
        if len(nums) % k != 0:
            return False
        target_set_count = len(nums) // k
        for num in nums:
            if len(D):
                prev_val, count = D.pop()
                if num == prev_val+1:
                    prev_val += 1
                    count += 1
                else:
                    D.appendleft((prev_val, count))
                    count = 1
            else:
                prev_val, count = num, 1
            if count < k:
                D.appendleft((prev_val, count))    
            if len(D) > target_set_count:
                break
        return len(D) == 0

# O(nlogn) time and O(n) space, exactly the same as Q846: Hand of straights
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k: return False
        if k==1: return True
        
        n = len(nums)
        cnt = collections.Counter(nums)
        heapify(nums)
        
        for i in range(n//k):
            start = heappop(nums)
            while cnt[start] == 0:
                start = heappop(nums)
            
            for i in range(k):
                if cnt[start+i] == 0: return False
                cnt[start+i] -= 1
                
        return True


class Solution:
    def isPossibleDivide(self, nums, k):
        ctr = collections.Counter(nums)
        for num in nums:
            start = num
            while ctr[start - 1]:
                start -= 1
            while start <= num:
                while ctr[start]:
                    for victim in range(start, start + k):
                        if not ctr[victim]:
                            return False
                        ctr[victim] -= 1
                start += 1
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n  ==1:
            return True
        if k==1:
            return True
        c = collections.Counter(nums)
        
        for num in nums:
            start = num
            while c[start-1]:
                start-=1
            
            while start<=num:
                while c[start]:
                    for j in range(k):
                        if not c[start+j]:
                            return False
                        c[start+j]-=1
                start+=1
        
        return True

import heapq
import collections
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        if len(nums) % k != 0:
            return False
        nums.sort()
        m = collections.defaultdict(list)
        
        for num in nums:
            left = m.get(num-1)
            right = m.get(num+1)
            if left and m[num-1][0] < k:
                curr = heapq.heappop(m[num-1])
                heapq.heappush(m[num], curr+1)
            elif right and m[num+1][0] <k:
                curr = heapq.heappop(m[num+1])
                heapq.heappush(m[num+1], curr+1)               
            else:
                heapq.heappush(m[num], 1)
            #print(m)

        for x in m:
            for i in m[x]:
                if i != k:
                    return False
        return True
    


import collections


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        num_of_sets = int(len(nums) / k)
        c = collections.deque([0] * num_of_sets)

        ct = {}
        for n in nums:
            ct[n] = ct.get(n, 0) + 1

        last_num = None
        for num in sorted(ct.keys()):
            if last_num is not None and num != last_num + 1 and any(cc != 0 for cc in c):
                return False

            amount = ct[num]
            for i in range(num_of_sets):
                if amount > 0:
                    c[i] = (c[i] + 1) % k
                    amount -= 1
                elif c[i] != 0:
                    return False

            if amount > 0:
                return False

            i = 0
            while c[0] == 0 and i < num_of_sets:
                c.append(c.popleft())
                i += 1

            last_num = num

        return all(cc == 0 for cc in c)


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        dic = Counter(nums)
        for x in sorted(nums):
            if x in dic:
                for y in range(x, x + k):
                    if y in dic:
                        dic[y] -= 1
                        if dic[y] == 0:
                            del dic[y]
                    else:
                        return False
        return True


import queue
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n%k != 0:
            return False
        dic = collections.defaultdict(list)
        nums = sorted(nums)
        for i, num in enumerate(nums):
            cur_length = heapq.heappop(dic[num-1]) if dic[num-1] and dic[num-1][0]!=k else 0
            heappush(dic[num],cur_length+1)

        for key in dic:
            for x in dic[key]:
                if x != k:
                    return False
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        freq = {}
        nums.sort()
        for n in nums:
            if n in freq:   
                freq[n]+=1
            else:
                freq[n]=1
        for num in freq:
            if freq[num]!=0:
                temp = freq[num]
                for i in range(num,num+k):
                    if i not in freq or freq[i]<temp:
                        return False
                    else:
                        freq[i]-=temp
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        M: Mapping[int, int] = {}
        for n in nums:
            if n in M:
                M[n] = M[n]+1
            else:
                M[n] = 1

        n = sorted(M.keys())[0]
        while True:
            for i in range(k):
                if n not in M or M[n] == 0:
                    return False
                M[n] = M[n] - 1
                n = n + 1

            for n in list(M.keys()):
                if M[n] == 0:
                    del (M[n])

            if len(list(M.keys())) == 0:
                return True

            n = sorted(M.keys())[0]


from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        d = Counter(nums)
        for x in sorted(nums):
            if x in d:
                for y in range(x, x + k):
                    if y in d:
                        d[y] -= 1
                        if d[y] == 0:
                            del d[y]
                    else:
                        return False
        return True
                
            
                


from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        d = Counter(nums)
        nums.sort()
        for x in nums:
            if x in d:
                for y in range(x, x + k):
                    if y in d:
                        d[y] -= 1
                        if d[y] == 0:
                            del d[y]
                    else:
                        return False
        return True
                
            
                


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        c = Counter(nums)
        while c:
            x = min(c.keys())
            for i in range(x,x+k):
                if i not in c: return False
                c[i] -= 1
                if c[i] == 0: del c[i]
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) == 0 or len(nums) % k != 0:
            return False
        counter = collections.Counter(nums)
        while counter:
            starter = min(counter.keys())
            
            for i in range(k):
                if starter + i not in counter:
                    return False
                else:
                    counter[starter+i] -= 1
                    if counter[starter+i] == 0:
                        del counter[starter+i]
                        
        
        return True
            


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
#         dq = deque()
#         #dq[i] = number of sequences with i elements, ending with current number
#         c = Counter(nums)
#         nums = sorted(set(nums))
#         current_num = 0
#         opening = 0
#         for i in range(len(nums)):
#             if i > 0 and nums[i] > nums[i - 1] + 1 and opening > 0:
#                 return False
#             if c[nums[i]] < opening:
#                 return False
#             dq.appendleft(c[nums[i]] - opening)
#             opening += c[nums[i]] - opening
#             if len(dq) >= k:
#                 opening -= dq.pop()
#         return opening == 0

        c = Counter(nums)
        nums = list(set(nums))
        heapify(nums)
        # print(list(set(nums)))
        print(nums)
        while nums:
            m = heappop(nums)
            while nums and c[m] == 0:
                m = heappop(nums)
            for i in range(1, k):
                if c[m + i] < c[m]:
                    print((c[m + i], c[m], m))
                    return False
                c[m + i] -= c[m]
            c[m] = 0
        return True
                    
            
                    
                
            


from collections import OrderedDict, Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if(len(nums) % k != 0):
            return False
        elems = sorted(list(set(nums)))
        count = OrderedDict()
        for elem in elems:
            count[elem] = 0
        for num in nums:
            count[num] += 1
        while(len(count) > 0):
            x = list(count.keys())[0]  
            for i in range(x,x+k):
                if(i not in count):
                    return False
                count[i] -= 1
                if(count[i] == 0):
                    del count[i]
        return True


from collections import Counter
from heapq import heappop, heapify

def is_possible_divide(heap, k):
    if len(heap) == 0:
        return True
    else:
        popped = []
        prev, min_count = heappop(heap)
        for i in range(k - 1):
            if not heap:
                return False
            else:
                value, count = heappop(heap)
                if value != prev + 1:
                    return False
                else:
                    count -= min_count
                    prev = value
                if count > 0:
                    popped.append((value, count))
        heap.extend(popped)
        heapify(heap)
        return is_possible_divide(heap, k)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        heap = [(value, count) for value, count in list(Counter(nums).items())]
        heapify(heap)
        return is_possible_divide(heap, k)


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        if len(nums) % k != 0:
            return False
        count = dict(Counter(nums))
        nums = sorted(list(set(nums)))
        for num in nums:
            if count[num] != 0:
                for i in range(1, k):
                    if num + i not in count:
                        return False
                    else:
                        count[num+i] -= count[num]
            count[num] = 0
           # print(count)
        return all([a == 0 for a in list(count.values())])


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums)%k != 0:
            return False
        
        m = int(len(nums)/k)
        
        res = []
        
        count = {}
        
        for i in range(len(nums)):
            if not count.get(nums[i]):
                count[nums[i]] = 0
            count[nums[i]] += 1
        
        arr = []
        for i in range(m):
            ks = list(count.keys()).copy()
            ks.sort()
            #print(count)
            for j in range(len(ks)):
                if len(arr) == 0 or arr[len(arr) - 1] == ks[j] - 1:
                    arr.append(ks[j])
                    count[ks[j]] -= 1
                    if count[ks[j]] == 0:
                        del count[ks[j]]
                else:
                    return False
                
                if len(arr) == k:
                    res.append(arr.copy())
                    arr.clear()
                    break
        if len(count) > 0:
            return False
        
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        W = k
        hand = nums
        
        hand.sort()
        mp = defaultdict(list)
        
        for elem in hand:
            prev_len = -1 if len(mp[elem - 1]) == 0 else heapq.heappop(mp[elem - 1])
            if prev_len == -1 or prev_len == W:
                heapq.heappush(mp[elem], 1)
            else:
                heapq.heappush(mp[elem], prev_len + 1)
                
        for key in mp.keys():
            for length in mp[key]:
                if length != W:
                    return False
                
        return True

from collections import defaultdict, OrderedDict
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums_dict = defaultdict(int)
        for num in nums:
            nums_dict[num] += 1
        
        nums_dict_ordered = OrderedDict(sorted(nums_dict.items()))
        
        while len(nums_dict_ordered) > 0:
            first = next(iter(nums_dict_ordered))
            nums_dict_ordered[first] -= 1
            if nums_dict_ordered[first] == 0:
                    del nums_dict_ordered[first]
            for val in range(1, k):
                check = first+val
                if check not in list(nums_dict_ordered.keys()) or  nums_dict_ordered[check] == 0:
                    return False
                else:
                    nums_dict_ordered[check] -= 1
                if nums_dict_ordered[check] == 0:
                    del nums_dict_ordered[check]
            
        return True


from collections import Counter
from heapq import heappop, heappush, heapify

def create_pairs(A):
    sorted_A = sorted(A)
    prev = sorted_A[0]
    pairs = [[prev, 1]]
    for curr in sorted_A[1:]:
        if curr !=  prev:
            pairs.append([curr, 1])
            prev = curr
        else:
            pairs[-1][1] += 1
    return [tuple(x) for x in pairs]

def is_possible_divide(heap, k):
    if len(heap) == 0:
        return True
    else:
        popped = []
        prev, min_count = heappop(heap)
        for i in range(k - 1):
            if not heap:
                return False
            else:
                value, count = heappop(heap)
                if value != prev + 1:
                    return False
                else:
                    count -= min_count
                    prev = value
                if count > 0:
                    popped.append((value, count))
        for val in popped:
            heappush(heap, val)
        # heap.extend(popped)
        # heapify(heap)
        return is_possible_divide(heap, k)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        heap = list(Counter(nums).items())
        # heap = create_pairs(nums)
        print(heap)
        heapify(heap)
        return is_possible_divide(heap, k)


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        N = len(nums)
        if (N % k != 0):
            return False
        
        counter = collections.Counter(nums)
        while (counter):
            min_key = min(counter.keys())
            for i in range(k):
                if (min_key in counter):
                    counter[min_key] -= 1
                    if (counter[min_key] == 0):
                        del counter[min_key]
                    min_key += 1
                else:
                    return False
        
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        counts = collections.Counter(nums)
        for num in nums:
            if counts[num] > 0:
                for i in range(k):
                    counts[num + i] -= 1
                    if counts[num + i] < 0:
                        return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if k == 1:
            return True
        if len(nums)%k:
            return False
        d = defaultdict(int)
        
        for n in nums:
            d[n] += 1
        
        count = 0
        iters = len(nums)//k
        
        while iters > 0:
            prev = None
            count = 0
            iters -= 1
            for key in sorted(d):
                # print(key,d, count,'here')
                if count != 0 and not count%k:
                    break
                if not prev or (d[key] > 0 and prev+1 == key):
                    d[key] -= 1
                    prev = key
                    count += 1
                else:
                    # print(d, count, '===')
                    return False
            # print(d,'---')
            a = list(d.keys())
            for key in a:
                if d[key] == 0:
                    d.pop(key)
        if len(list(d.keys())):
            return False
        return True


class Solution:
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        heapify(nums)
        
        if len(Ct) > len(nums)*0.9:                               
            return self.isNStraightHand(nums, k)

        while Ct:
            start = heappop(nums)
            while not Ct[start]:
                start = heappop(nums)
            for i in range(start, start + k):
               # print(num+i)
                if not Ct[i]: return False
                if Ct[i] == 1: del Ct[i]
                else: Ct[i] -= 1
                
        return True


    def isNStraightHand(self, hand, W):
      #  heapify(hand)
        
        while hand:
            last_item = heappop(hand)
            leftover = []
            
            for _ in range(W - 1):
                if not hand: return False                
                next_item = heappop(hand)
                
                while next_item == last_item:
                    leftover.append(next_item)
                    if not hand: return False                       
                    next_item = heappop(hand)
                    
                if next_item > last_item + 1: return False                    
                last_item = next_item                
            for item in leftover:
                heappush(hand, item)
                
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counter = collections.Counter(nums)
        for n in sorted(counter):
            num = counter[n]
            if num > 0:
                for i in range(k):
                    counter[n+i]-=num
                    if counter[n+i]<0:
                        return False
        return True

from collections import defaultdict, Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if not nums:
            return False
        elif not k:
            return True
        counter = Counter(nums)
        while counter:
            start, count = sorted(counter)[0], 0
            while count < k:
                if counter[start] == 0:
                    return False
                counter[start] -= 1
                if not counter[start]:
                    counter.pop(start)
                start += 1
                count += 1
        return not counter

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        
        #start = 10**9
        #end = 1
        
        v_cnt = collections.defaultdict(int)
        for v in nums:
            v_cnt[v] += 1
            
        for v in sorted(v_cnt.keys()):
            if v_cnt[v] == 0:
                continue
            else:
                l = v_cnt[v]
                for nv in range(v+1, v+k):
                    if v_cnt[nv] < l:
                        return False
                    v_cnt[nv] -= l
        
        return True

class Solution:
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        heapify(nums)
        
        if len(Ct) > len(nums)*0.75:                               
            return self.isNStraightHand(nums, k)

        while Ct:
            start = heappop(nums)
            while not Ct[start]:
                start = heappop(nums)
            for i in range(start, start + k):
               # print(num+i)
                if not Ct[i]: return False
                if Ct[i] == 1: del Ct[i]
                else: Ct[i] -= 1
                
        return True


    def isNStraightHand(self, hand, W):
      #  heapify(hand)
        
        while hand:
            last_item = heappop(hand)
            leftover = []
            
            for _ in range(W - 1):
                if not hand: return False                
                next_item = heappop(hand)
                
                while next_item == last_item:
                    leftover.append(next_item)
                    if not hand: return False                       
                    next_item = heappop(hand)
                    
                if next_item > last_item + 1: return False                    
                last_item = next_item                
            for item in leftover:
                heappush(hand, item)
                
        return True

#counter
#

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        
        counter = collections.Counter(nums)
        keys = sorted(counter)
        print(keys)
        for i in keys:
            while i in counter:
                cur = i
                counter[cur] -= 1
                if not counter[cur]:
                    del counter[cur] 
                for _ in range(k - 1):
                    if cur + 1 in counter:
                        cur += 1
                        counter[cur] -= 1
                        if not counter[cur]:
                            del counter[cur] 
                    else:
                        return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums.sort()
        h = []
        for num in nums:
            tmp = []
            found = False
            while h:
                max_idx, min_idx = heapq.heappop(h)
                if max_idx > num - 1:
                    tmp.append((max_idx, min_idx))
                    break  
                
                if max_idx == num - 1:
                    found = True
                    if max_idx - min_idx + 2 == k:
                        break
                    
                    heapq.heappush(h, (max_idx + 1, min_idx))
                    
                    break
                tmp.append((max_idx, min_idx))
                
            for item in tmp:
                heapq.heappush(h, item)
            
            if found:
                continue
            
            if k != 1:
                heapq.heappush(h, (num, num))

        return not h

from collections import defaultdict, Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if(len(nums) % k != 0):
            return False
        elems = sorted(list(set(nums)))
        count = defaultdict(int)
        for elem in elems:
            count[elem] = 0
        for num in nums:
            count[num] += 1
        while(len(count) > 0):
            x = list(count.keys())[0]  
            for i in range(x,x+k):
                if(count[i] == 0):
                    return False
                count[i] -= 1
                if(count[i] == 0):
                    del count[i]
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        nums.sort()
        counts = collections.Counter(nums)
        
        for x in nums:
            if counts[x] == 0:
                continue
            exist_chain = True
            for i in range(k):
                if counts[x+i] == 0:
                    return False
                counts[x+i] -= 1
        
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        l=nums[::]
        l.sort()
        n=len(l)
        d=Counter(l)
        count=0
        for i in range(n):
            if d[l[i]]!=0:
                d[l[i]]-=1
                f=0
                for j in range(l[i]+1,l[i]+k):
                    if d[j]==0:
                        f=1
                        break
                    d[j]-=1
                if f==1:
                    return False
        return True
                    
               
                        
                        
                        
                        
                
        
        
        


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k > 0:
            return False

        # Starting at smallest number, remove sequences of size k
        d = {}
        
        for num in nums:
            d[num] = d.get(num, 0) + 1

        for num in nums:
            if d[num] > 0 and (num-1 not in d or d[num-1] < d[num]):
                # num is start of a sequence; try removing k
                for _ in range(k):
                    if num not in d or d[num] == 0:
                        return False
                    d[num] -= 1
                    num += 1
        
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counter = Counter(nums)
        heap_nums=[]
        groups=[]
        for key, val in counter.items():
            heapq.heappush(heap_nums,(key,val))
        
        while(heap_nums):
            count=0
            sub_group=[]
            remaining_elements=[]
            while(count<k):
                if not heap_nums:
                    return False
                popped_elem=heapq.heappop(heap_nums)
                if popped_elem[1]-1>0:
                    remaining_elements.append(popped_elem)
                if not sub_group:
                    sub_group.append(popped_elem[0])
                else:
                    if popped_elem[0]-1 == sub_group[-1]:
                        sub_group.append(popped_elem[0])
                    else:
                        return False
                count+=1

            groups+=sub_group
            for elem in remaining_elements:
                heapq.heappush(heap_nums,(elem[0],elem[1]-1))

        return True

from collections import deque, Counter

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counter = Counter(nums)
        q = deque()
        lowest = 0
        nums = sorted(set(nums))
        for i in range(len(nums)):
            if i and nums[i] != nums[i - 1] + 1 and lowest:
                return False
            
            diff = counter[nums[i]] - lowest
            if diff < 0:
                return False
            
            if diff > 0:
                q.appendleft((i + k - 1, diff))
                
            lowest = counter[nums[i]]
            
            if q[-1][0] == i:
                lowest -= q.pop()[1]
            
        return not q

from collections import Counter
from heapq import heappop, heappush, heapify

def create_pairs(A):
    sorted_A = sorted(A)
    prev = sorted_A[0]
    pairs = [[prev, 1]]
    for curr in sorted_A[1:]:
        if curr !=  prev:
            pairs.append([curr, 1])
            prev = curr
        else:
            pairs[-1][1] += 1
    return [tuple(x) for x in pairs]

def is_possible_divide(heap, k):
    if len(heap) == 0:
        return True
    else:
        popped = []
        prev, min_count = heappop(heap)
        for i in range(k - 1):
            if not heap:
                return False
            else:
                value, count = heappop(heap)
                if value != prev + 1:
                    return False
                else:
                    count -= min_count
                    prev = value
                if count > 0:
                    popped.append((value, count))
        for val in popped:
            heappush(heap, val)
        # heap.extend(popped)
        # heapify(heap)
        return is_possible_divide(heap, k)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        # heap = list(Counter(nums).items())
        heap = create_pairs(nums)
        print(heap)
        heapify(heap)
        return is_possible_divide(heap, k)


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums)%k!=0:
            return False
        nums.sort()
        #print(nums,k)
        d={}
        for i in nums:
            d[i]=d.get(i,0)+1
        for j in d:
            while d[j]>0:
                for x in range(j,j+k):
                    if d.get(x,0)>0:
                        d[x]-=1
                    else:
                        return False
        return True
        
        
        '''
        i=0
        while k<=len(nums):
            a=nums[0]
            for j in range(k):
                if a+j not in nums or len(nums)==0:
                    return False
                nums.remove(a+j)
            if len(nums)%k!=0:
                return False
            if len(nums)==0:
                return True
        return True
        
        while True :
            a=nums[0]
            for i in range(k):
                if a+i not in nums or len(nums)==0:
                    return False
                nums.remove(a+i)
            if len(nums)%k!=0:
                return False
            if len(nums)==0:
                return True
        '''

from collections import Counter

class Solution:
    '''
    Good use of counter
    Same can be done in complex way with sorting the array and using orderedDict
    '''
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        c = Counter(nums)
        while c:
            m = min(c)
            for i in range(m, m+k):
                if i not in c:
                    return False
                elif c[i] == 1:
                    del c[i]
                else:
                    c[i] -= 1
                    
        return True
                


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0 or len(nums) < k:
            return False
        from collections import Counter
        import heapq
        
        d = Counter(nums)
        num_groups = len(nums) // k
        h = [(i,c) for i,c in d.items()]
        heapq.heapify(h)

        while len(h) > 0:
            temp = []
            k_= k
            while k_ > 0:
                if h:
                    x,c = heapq.heappop(h) # pop the smallest element
                    #if d[x] > 0:
                    if temp:
                        if temp[-1] == x - 1:
                            temp.append(x)
                        else:
                            return False
                    else:
                        temp.append(x)
                else:
                    return False
                
                d[x] -= 1
                k_ -= 1
            for x in temp:
                if d[x] > 0:
                    heapq.heappush(h,(x,d[x]))
            
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = collections.Counter(nums)
        que = collections.deque()
        last_required = 0
        last_num = 0
        for num, num_count in sorted(count.items()):
            if last_required > 0 and last_num + 1 != num or num_count < last_required:
                return False
            que.append(num_count - last_required)
            last_required = num_count
            if len(que) == k:
                last_required -= que.popleft()
            last_num = num
        return last_required == 0
            
    
    
    def isPossibleDivide_II(self, nums: List[int], k: int) -> bool:
        count = collections.Counter(nums)
        for next_num in sorted(count):
            next_dup = count[next_num]
            for j in range(next_num, next_num + k):
                if count[j] < next_dup:
                    return False
                count[j] -= next_dup
        return True

class Solution:
    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        if len(hand) % W:
            return False
        cnt = Counter(hand)
        cards = sorted(cnt)
        while True:
            first = cards.pop()
            if not cnt[first]:
                continue
            elif cnt[first] > 1 :        
                cnt[first] -= 1
                cards.append(first)
            else:
                del cnt[first]
            for i in range(first - 1, first - W, -1):
                if not cnt[i]:
                    return False
                elif cnt[i] > 1:
                    cnt[i] -= 1
                else:
                    del cnt[i]
            if not cnt:
                return True
        return False # never happen

from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
                
        cnums = Counter(nums)
        nums.sort()
        
        for i in nums:
            if cnums[i] == 0:
                continue
            
            for j in range(i, i+k):
                if cnums[j] == 0:
                    return False
                cnums[j] -= 1
        
        return True        
                
                
            
            
            
            


from collections import Counter
from heapq import heappop, heapify

def create_pairs(A):
    sorted_A = sorted(A)
    prev = sorted_A[0]
    pairs = [[prev, 1]]
    for curr in sorted_A[1:]:
        if curr !=  prev:
            pairs.append([curr, 1])
            prev = curr
        else:
            pairs[-1][1] += 1
    return [tuple(x) for x in pairs]

def is_possible_divide(heap, k):
    if len(heap) == 0:
        return True
    else:
        popped = []
        prev, min_count = heappop(heap)
        for i in range(k - 1):
            if not heap:
                return False
            else:
                value, count = heappop(heap)
                if value != prev + 1:
                    return False
                else:
                    count -= min_count
                    prev = value
                if count > 0:
                    popped.append((value, count))
        heap.extend(popped)
        heapify(heap)
        return is_possible_divide(heap, k)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        # heap = list(Counter(nums).items())
        heap = create_pairs(nums)
        print(heap)
        heapify(heap)
        return is_possible_divide(heap, k)


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        count = collections.Counter(nums)
        
        heap = []
        for (num, cnt) in count.items():
            heapq.heappush(heap, (num, cnt))
            
        while heap:
            nums, cnts = [], []
            for _ in range(k):
                if not heap:
                    return False
                else:
                    (num, cnt) = heapq.heappop(heap)
                    nums.append(num)
                    cnts.append(cnt)
                    
            if not all(b == a + 1 for (a, b) in zip(nums, nums[1:])):
                return False
            
            for (num, cnt) in zip(nums, cnts):
                if cnt > 1:
                    heapq.heappush(heap, (num, cnt - 1))
                    
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        numDict = {}
        for num in nums:
            if str(num) in numDict:
                numDict[str(num)] +=1
            else:
                numDict[str(num)] = 1
        
        for key in sorted(list(numDict.keys()), key= lambda x: int(x)):
            val = numDict[key]
            if val == 0:
                continue
            for i in range(1, k):
                if str(int(key)+i) not in numDict:
                    return False
                temp = numDict[str(int(key)+i)] - val
                if temp < 0:
                    return False
                numDict[str(int(key)+i)] = temp
                
        
        return True


#counter, delete them one-by-one
#{1:1, 2:2, 3:3, 4:2, 5:1, 9:1, 10:1, 11:1}
from collections import Counter
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        counter = Counter(nums)
        for num in sorted(counter.keys()):
            count = counter[num]
            if count == 0:
                continue
            for i in range(num, num+k):
                counter[i] -= count
                if counter[i] < 0:
                    return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0 or len(nums) < k:
            return False
        from collections import Counter
        import heapq
        
        d = Counter(nums)
        num_groups = len(nums) // k
        h = [(i,c) for i,c in d.items()]
        heapq.heapify(h)

        while len(h) > 0:
            temp = []
            k_= k
            while k_ > 0:
                if h:
                    x,c = heapq.heappop(h) # pop the smallest element
                    #if d[x] > 0:
                    if temp:
                        if temp[-1] == x - 1:
                            temp.append(x)
                        else:
                            return False
                    else:
                        temp.append(x)
                else:
                    return False
                
                d[x] -= 1
                k_ -= 1
            print(temp)
            for x in temp:
                if d[x] > 0:
                    heapq.heappush(h,(x,d[x]))
            
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        import collections
        c = collections.Counter(nums)
        for i in sorted(c):
            if c[i] > 0:
                for j in range(k)[::-1]:
                    c[i + j] -= c[i]
                    if c[i + j] < 0:
                        return False
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums)%k!=0:
            return False
        candidates=collections.Counter(nums)
        keys=list(candidates.keys())
        keys.sort()
        i=0
        while i<len(keys):
            x=keys[i]
            if candidates[x]==0:
                i+=1
            else:
                temp=1
                candidates[x]-=1
                while temp<k:
                    if candidates[x+temp]>0:
                        candidates[x+temp]-=1
                        temp+=1
                    else:
                        return False
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        count=collections.Counter(nums)
        print(count)
        nums.sort()
        for x in nums:
            if count[x]==0:
                continue
                
            else:
                for i in range(1,k):
                    print(x,x+i)
                    if count[x+i]>0:
                        count[x+i]-=1
                    elif count[x-i]>0:
                        count[x-i]-=1
                        
                    else:
                        return False
            count[x]-=1
                    
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        q = collections.deque()
        opened, prev = 0, -1
        cnt = collections.Counter(nums)
        for ele in sorted(cnt):
            if cnt[ele] < opened or opened > 0 and ele > prev + 1:
                return False
            q.append(cnt[ele] - opened)
            prev = ele
            opened = cnt[ele]
            if len(q) == k: opened -= q.popleft()
        return opened == 0
            
        
#1:3
#2:2
#3:1
#4:1
#k=4
#q=[3,-1,-1,0]
#1
#1 2
#1 2 3
#4


class Solution:                
    
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:        
        import heapq
        heap = []
        hm = {}
        for i in nums:
            if i not in hm:
                hm[i] = 0
            hm[i] += 1
            
        for i in hm:
            heapq.heappush(heap, (i, hm[i]))
            
        while len(heap):
            pending = []
            x = heapq.heappop(heap)
            if x[1] - 1 > 0:
                pending.append((x[0], x[1] - 1))
            
            cnt = 1
            last = x[0]
            while cnt < k:
                if len(heap) == 0 or heap[0][0] != last + 1:
                    return False
                n = heapq.heappop(heap)
                if n[1] - 1 > 0:
                    pending.append((n[0], n[1]-1))
                last = n[0]
                cnt += 1
            for x in pending:
                heapq.heappush(heap, x)
        return True
        
                
        
                
            
            
                
            
        
        
        
        
        
        
                
                
        
    


class Solution:
  def isPossibleDivide(self, nums, k):
    d = collections.Counter(nums)
    roots = [n for n in d if not d[n - 1]]
    for r in roots:
        for i in reversed(range(r, r + k)):
            if d[i] < d[r]:
              return False
            d[i] -= d[r]
            if not d[i] and d[i + 1]:
                roots.append(i + 1)
    return True

class Solution:
    def isPossibleDivide(self, nums, k: int) -> bool:
        if not nums or not k:
            return False

        c = Counter(nums)
        nums.sort()
        for num in nums:
            if num not in c:
                continue
            for i in range(k):
                if num + i in c and c[num + i] > 0:
                    c[num + i] -= 1
                    if c[num + i] == 0:
                        del c[num + i]
                else:
                    return False
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums)%k!=0:
            return False
        c=Counter(nums)
        keys=sorted(c)
        for key in keys:
            while c[key]>0:
                for i in range(k):
                    if key+i in list(c.keys()) and c[key+i]>0:
                        c[key+i]-=1
                    else:
                        return False
        return True

                
                    


from typing import List
from collections import Counter
from sortedcontainers import SortedSet

class Solution:
    def isPossibleDivide(self, hand: List[int], W: int) -> bool:
        # print('-----')
        # print(f'hand: {hand}')
        # print(f'W: {W}')

        if not hand:
            return True
        elif len(hand) % W != 0:
            return False
        else:
            counts = Counter(hand)
            ns = SortedSet(list(counts.keys()))

            numRounds = len(hand) // W
            for r in range(numRounds):
                if len(ns) < W:
                    return False
                else:
                    nn = list(ns.islice(stop=W))
                    # print(f'r={r} nn={nn} ns={ns} counts={counts}')
                    prev = ns[0] - 1
                    for n in nn:
                        if n == prev + 1:
                            counts[n] -= 1
                            if counts[n] == 0:
                                ns.remove(n)
                            prev = n
                        else:
                            return False

            return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        freq = Counter(nums)
        
        start = []
        for n,v in freq.items():
            if freq[n-1] == 0:
                start.append(n)
        
        while start:
            
            num = start.pop()
            
            if freq[num] == 0:
                continue
            else:
                for t in range(num+k-1,num-1,-1):
                    if freq[t] < freq[num]:
                        return False
                    freq[t] -= freq[num]
                    if freq[t] == 0 and freq[t+1] > 0:
                        start.append(t+1)

        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = collections.Counter(nums)
        
        if len(count):
            start = min(count)

            while len(count):
                #print(count)
                if count[start] == 0:
                    start = min(count)
                for num in range(start, start+k):
                    if count[num]:
                        count[num] -=1
                    else:
                        return False
                    if count[num] == 0:
                        del count[num]
                        start +=1
                        
            return True
        
        return False

class Solution:
  # 456 ms
    def isPossibleDivide(self, nums, k):
        if len(nums) % k: return False
        Ct = Counter(nums)
        keys = list(Ct.keys())
        heapify(keys)
        num = heappop(keys)
        
        while Ct:
            while not Ct[num]:
                num = heappop(keys)
            for i in range(k):
               # print(num+i)
                if not Ct[num+i]: return False
                if Ct[num+i] == 1: del Ct[num+i]
                else: Ct[num+i] -= 1
                
        return True

class Solution:
  def isPossibleDivide(self, nums, k):
    ctr = Counter(nums)
    for num in nums:
        start = num
        while ctr[start - 1]:
            start -= 1
        while start <= num:
            times = ctr[start]
            if times:
                for victim in range(start, start + k):
                    if ctr[victim] < times:
                        return False
                    ctr[victim] -= times
            start += 1
    return True

import collections 


class Solution(object):
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        if not nums:
            return False
        
        if len(nums)%k != 0:
            return False
        
        count_map = collections.Counter(nums)
        
        while count_map:
            min_ele = min(count_map)
            
            for i in range(k):
                key_count = count_map.get(min_ele+i, None)
                if not key_count:
                    return False
                
                if key_count == 1:
                    del count_map[min_ele+i]
                else:
                    count_map[min_ele+i] -= 1
                    
        
        return True

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
#         if len(nums) % k or len(nums) < k:
#             return false
        
#         ktrack = 0
        
#         nums.sort()
        
#         for n in nums:
        nums.sort()
        
        index = {}
        for i in nums:
            index[i] = index.get(i,0) + 1
            
        for i in index:
            # subtracting from dict count until nothing left
            # k-size lists must be asc
            while index[i] > 0:
                # creating window for k-size list
                for j in range(i,i+k):
                    # if j still has any left, decrement
                    if index.get(j,0) > 0:
                        index[j] -= 1
                    else:
                        return False
        return True


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = defaultdict(int)
        for n in nums:
            count[n] += 1
        
        for n in sorted(count):
            if count[n] == 0:
                continue
            
            occ = count[n]
            count[n] = 0
            for i in range(n+1, n+k):
                count[i] -= occ
                if count[i] < 0:
                    return False
        
        return True
        


class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        
        l = len(nums)
        
        if l%k!=0:
            return False
        
        g = int(l//k)
        
        num_dict = dict()
        for num in nums:
            num_dict[num] = num_dict.get(num, 0) + 1
        
        for i in range(g):
            val = min(num_dict.keys())
            if num_dict[val]==1:
                del num_dict[val]
            else:
                num_dict[val] -= 1
            
            for j in range(1, k):
                val += 1
                if val not in num_dict:
                    return False
                elif num_dict[val]==1:
                    del num_dict[val]
                else:
                    num_dict[val] -= 1
        
        return True
                    
    



class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        count = collections.defaultdict(int)
        nums.sort()
        for n in nums:
            if count[n] == 0:
                for i in range(1,k):
                    count[n+i] += 1
            else:
                count[n] -= 1
        for c in count.values():
            if c>0:
                return False
        return True