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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

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
		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:

	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):
				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:

	def isPossibleDivide(self, nums: List[int], k: int) -> bool:
		if k == 1:
			return True
		N = len(nums)
		if N % k:
			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]
				queue.append(new_group)
			else:
				current = queue.pop(0)
				last_num = current[0]
				size = current[1]
				if last_num == num - 1:
					if size == k - 1:
						continue
					else:
						size += 1
						update_group = [num, size]
						queue.append(update_group)
				elif last_num == num:
					new_group = [num, 1]
					queue.append(current)
					queue.append(new_group)
				else:
					return False
		if len(queue) == 0:
			return True
		else:
			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)
		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:

	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:

	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):
				if not c[num + i]:
					return False
				c[num + i] -= 1
		return True


class Solution:

	def isPossibleDivide(self, nums: List[int], k: int) -> bool:
		c = collections.Counter(nums)
		q = collections.deque()
		while c:
			for key in c:
				if key - 1 not in c:
					q.append(key)
			while 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
				elif count[i] == 1:
					del count[i]
				else:
					count[i] -= 1
		return True


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:
			if count[n] != 0:
				for v in range(n, n + k):
					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]
		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


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


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:

	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, 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


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:
		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:
		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:
					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


class Solution:

	def isPossibleDivide(self, nums: List[int], k: int) -> bool:
		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


def isPossibleDivide(nums, k):
	if len(nums) % k != 0:
		return False
	else:
		nums.sort()
		return decreaseConquer(nums, k)

def decreaseConquer(A, k):
	if len(A) == 0:
		return True
	else:
		pivot = A[len(A) - 1]
		for i in range(k):
			j = binarySearch(A, 0, len(A) - 1, pivot - i)
			if j == -1:
				return False
			else:
				del A[j]
		return decreaseConquer(A, k)

def binarySearch(S, l, r, x):
	if l <= r:
		mid = l + (r - l) // 2
		if S[mid] == x:
			return mid
		elif S[mid] > x:
			return binarySearch(S, l, mid - 1, x)
		else:
			return binarySearch(S, mid + 1, r, x)
	else:
		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:
		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


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:
		sorted_counter = OrderedDict(Counter(sorted(hand)))
		queue = list(sorted_counter.keys())
		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:
		countMap = {}
		for num in nums:
			countMap[num] = countMap.get(num, 0) + 1
		keyList = sorted(countMap.keys())
		while len(keyList) > 0:
			if len(keyList) < k:
				return False
			remove = []
			for i in range(k):
				if i > 0 and keyList[i] - keyList[i - 1] > 1:
					return False
				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


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


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
		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:
		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


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: 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)
		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


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:
		c = Counter(nums)
		nums = list(set(nums))
		heapify(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
		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()
			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)
		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())
		print(heap)
		heapify(heap)
		return is_possible_divide(heap, k)


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):
				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:
					return False
			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):
				if not Ct[i]:
					return False
				if Ct[i] == 1:
					del Ct[i]
				else:
					Ct[i] -= 1
		return True

	def isNStraightHand(self, hand, W):
		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
		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: 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


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
		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]):
				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])
				elif 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


class Solution:

	def isPossibleDivide(self, nums: List[int], k: int) -> bool:
		if len(nums) % k != 0:
			return False
		nums.sort()
		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


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)
					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


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


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


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:
			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


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:
		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))
					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):
				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


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:
		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