Divide Array in Sets of K Consecutive Numbers

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].

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].

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

---

Sorted HashMap

Python's dictionaries are ordered, meaning the order that keys are placed into the dictionary will stay intact.  

Knowing this, we can sort the input list, count the frequency of each character within the dictionary, then iteratively move through the dictionary starting from the minimum value to check whether each next value within the k sequence exists.  

We'll do this until we have decremented each value frequency to zero, in which case we will delete the keys.

---

First off, if the length of the input array isn't divisible by k, then it would be impossible for us to divide the array evenly into sets of k sequences.

If this is the case then we will return false.

        if len(nums) % k != 0:
            return False

 

Otherwise, we will sort the input array and initialize our dictionary.

        nums.sort()
        seen = {}

 

For each number from the input array, if that number hasn't already been seen then we will initialize it into our dictionary with a frequency value of one.

Otherwise, we will increment the frequency value.

        for num in nums:
            if num in seen:
                seen[num] += 1
            else:
                seen[num] = 1

 

Then, while we still have values in our dictionary, we will get the minimum value and try to see if we have a consecutive sequence of size k, starting from that value.

If not, we will return false.

        while seen:
            min_val = min(seen.keys())
            for i in range(min_val, min_val + k):
                if i not in seen:
                    return False

 

After we see a value, we will decrement its frequency so that we don't use it in more sequences than we're able to.

If that frequency has been decremented to zero then we will delete the key so that we know we can't use it anymore in the future.

                seen[i] -= 1
                if seen[i] == 0:
                    del seen[i]

 

If we have successfully checked off each number, we will return true.

        return True

---

---

Heap

The previous solution took advantage of Python's ordered dictionary and view objects (.keys()), which allowed for the values in the dictionary to not have to be copied within each iteration.

Without language specificity, we could also come up with a solution that utilizes a heap.  This may be more intuitive since we are iteratively building a sequence that requires us to have constant access to the current minimum value, which is the whole idea behind a min-heap.

What we can do is count the frequencies of the values as we did in the previous solution, but from there we will push each value and frequency into a heap.  

Once we have done that, we will build the subarrays using the top k values from the heap then go through these subarrays and check that they are consecutive.

---

First off, if the length of the input array isn't divisible by k, then it would be impossible for us to divide the array evenly into sets of k sequences.

If this is the case then we will return false.

        if len(nums)%k != 0:
            return False

 

Otherwise, let's initialize our heap and dictionary.

        seen, heap = {}, []

 

For each number from the input array, if that number hasn't already been seen then we will initialize it into our dictionary with a frequency value of one.

Otherwise, we will increment the frequency value.

        for num in nums:
            if num not in seen:
                seen[num] = 1
            else:
                seen[num] += 1

 

Next, for each number within our dictionary and its frequency, we will push it into our heap with the number being first in the tuple so that the heap sorts on values and not frequencies.

        for num in seen:
            heapq.heappush(heap, (num, seen[num]))

 

Now we will simulate building these subarrays through the use of buckets.

We'll continue while we still have values in our heap.

        while heap:
            bucket = []

 

Let's pop off the top k numbers and place them into the bucket.

However, if we have emptied the heap and have less than k values in our bucket, then that means we don't have enough numbers to build a consecutive subarray from so we will return false.

            for _ in range(k):
                if len(bucket) < k and not heap:
                    return False
                bucket.append(heapq.heappop(heap))

 

Otherwise, we'll step through the bucket we just made and verify all of the values are consecutive.

We'll be comparing each value with its previous value so we will start from the second index.

            for i in range(1, len(bucket)):

 

If the two numbers aren't consecutive then we will return false.

                if bucket[i][0] != bucket[i-1][0] + 1:
                    return False

 

If they are, then we will continue to cycle back numbers from the bucket into the heap.

If the previous number frequency is greater than one then we will need to cycle it back into the heap, decrementing its frequency by one since we just used it.  The reason why we are waiting to cycle back until we have filled the buckets is we don't want two of the same minimum value to end up in the same bucket, this ensures we are getting one of each.

                if bucket[i-1][1] > 1:
                    heapq.heappush(heap, (bucket[i-1][0], bucket[i-1][1] - 1))

 

Also, if we are at the last value in the bucket then we will check if we need to cycle it back as well.

                if i == len(bucket) - 1:
                    if bucket[i][1] > 1:
                        heapq.heappush(heap, (bucket[i][0], bucket[i][1] - 1))

 

If we never returned false then we were able to build the consecutive subarrays through these buckets.

        return True

---