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