Divide Array in sets of k consecutive numbers

Given an array of size n and a value k. Determine whether it is possible to divide the array into sets of k consecutive numbers.

Example Test Cases

Sample Test Case 1

Input Array: 1, 2, 5, 6
K: 2
Expected Output: True
Explanation: This is because we can divide the array as follows [1,2] and [5, 6]

Sample Test Case 2

Input Linked List: 1, 2, 1, 2, 3, 3, 10, 11, 12
K: 3
Expected Output: True
Explanation: This is because, we can divide the array as follows [1, 2, 3] , [1, 2, 3 ] and [10, 11, 12]

Solution

We can solve this problem by simulating the creation of sets. Clearly, at any point in time, the smallest available number in the array needs to be the start of some set. Let that number be i . Group creation is only possible if all the numbers from i , i + 1 , i + 2 … i + k - 1 are available in the array.
For example, in the first test case 1, 2, 5, 6 , the smallest available number is 1 . So, it has to be the start of some group, since 2 will also become a part of the same group, the remaining elements after 1 and 2 are eliminated is 5 and 6 . The smallest available number out of those is 5 which needs to be a start of some other group. We will keep on simulating this process, till we remove all the elements or we are unable to form the group.

To implement this solution, we can use a hash table to store the counts of each available element and try to simulate the above algorithm. Take a look at the code below:

Implementation

#include <bits/stdc++.h>
using namespace std;

bool isPossibleDivide(vector& nums, int k) {
    int n = nums.size();
    if (n%k > 0) {
        return false;
    }
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        mp[nums[i]]++;
    }
    while (mp.size() > 0) {
        auto it = mp.begin();
        int elem = it->first;
        int total = it->second;
        for(int i = elem; i < elem + k; i++) {
            if (mp[i] < total) return false;
            else mp[i] -= total;
            if (mp[i] == 0) {
                if (i != it->first) {
                    return false;
                }
                else {
                    // Since the count has become zero for the element, remove it.
                    mp.erase(it);
                    it = mp.begin();
                }
            }
        }
    }
    return true;
}

int main() {
    vector v = { 1, 1, 2, 3, 2, 5, 6,4 };
    int k = 2;
    cout << isPossibleDivide(v, k) << "\n";
    return 0;
}