# 1296. Divide 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.
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.
# Solution
Approach 1: use a hashtable (python Counter) to store frequencies of letters. Starting from the min value of the counter each time.
Approach 2: same idea with frequencies, but for each number, go down to get the min of the streak, then go up for k nums. Time: O(N)
.
# Code (Python)
Approach 1:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
# idea: starting from the min value of the counter each time
bag = {}
for num in nums:
if num not in bag:
bag[num] = 0
bag[num] += 1
while bag:
min_val = min(bag.keys())
for i in range(min_val, min_val + k):
if i not in bag or bag[i] <= 0:
return False
bag[i] -= 1
if bag[i] == 0:
bag.pop(i)
return True
Approach 2:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
# idea: for each number, go down to get the min of the streak, then go up for k nums -- O(N)
bag = collections.Counter(nums)
for num in nums:
start = num
while bag[start - 1] > 0:
start -= 1
# strikes out all starts lower than the num
while start <= num:
num_repeat = bag[start]
if num_repeat > 0:
for i in range(start, start + k):
bag[i] -= num_repeat
if bag[i] < 0:
return False
start += 1
return True
# Code (C++)
Approach 1:
Approach 2: