Solution
Approach 1
We can employ a greedy approach where we start from the smallest number in the array, say minNum, and check whether minNum+1, minNum+2, …minNum+k-1 exist and then so on for next smallest number. For this, we can do the following:
- Count number of different numbers to a map (map stores number->frequency)
- Loop from the smallest number in the map
- Everytime we meet a new number i, we decrement frequency of numbers from i to i+k-1. If any number does not exist, we return false.
Code:
bool isPossibleDivide(vector<int> A, int k) {
map<int, int> c;
for (int i : A) c[i]++;
for (auto it : c)
if (c[it.first] > 0)
for (int i = k - 1; i >= 0; --i)
if ((c[it.first + i] -= c[it.first]) < 0)
return false;
return true;
}
But this approach can be expensive when k is very large as the time taken is O(MlogM + MK) (MlogM for the map), where M is the number of different numbers in the array.
Approach 2
The question can be solved using a more general approach where we won’t have to look forward K-1 elements for each new element encountered. We can use a queue to store which stores for each element the minimum frequency of next K-1 elements it expects to have (i.e., for each element the number of K size arrays it will form as the first element in that array). Suppore the array is [1,2,2,3,3,4] and K=3 then for 1 we store 1 in queue (as it is expected to form [1,2,3]), for 2 we also store 1 (it is expected to form [1,2,3] and [2,3,4] but only [2,3,4] starts with 2), for 3 we will store 0 (it is expected to form [1,2,3] and [2,3,4] but none starts with 3), for 4 we store 0 (it is expected to form [2,3,4] and it doesn’t start with 4).
- Count number of different elements to a map as in previous approach
- “opened” represent current open straight groups (eg: when we come at 3, we are expecting groups starting from 1 and 2 to be there so opened=2)
- In a queue, we record the number of straight group the element opens (= frequency of that element - opened. In the above example, when we come to 3, frequency(3)=2 and opened=2 so this means 3 will be used in both groups so it will not start any group of its own so we push 0 to queue)
Note that when queue’s size reaches K, this means that the group of first element in queue has been completed. So we pop that element and update “opened”. Eg: when we reach 3 above, opened=2 initially and after pushing 3’s frequency-opened queue size = 3. Now, this means that we have to pop the first element (=1). This is because the group [1,2,3] has been completed. We update opened: opened = opened - queue.front().
bool isPossibleDivide(vector<int>& nums, int k) {
map<int, int> c;
for (int i : nums)
c[i]++;
queue<int> start;
int last_checked = -1, opened = 0;
for (auto it : c) {
int i = it.first;
if (opened > 0 && i > last_checked + 1 || opened > c[i]) return false;
start.push(c[i] - opened);
last_checked = i, opened = c[i];
if (start.size() == k) {
opened -= start.front();
start.pop();
}
}
return opened == 0;
}
Time complexity: O(MlogM)