Divide Array in Sets of K Consecutive Numbers
Problem
Given an integer array nums and an integer k, determine whether nums can be partitioned into groups of k consecutive integers. Return true if possible.
nums = [1, 2, 3, 3, 4, 4, 5, 6], k = 4truefrom collections import Counter
def is_possible_divide(nums, k):
if len(nums) % k: return False
count = Counter(nums)
for x in sorted(count):
c = count[x]
if c == 0: continue
for j in range(k):
if count[x + j] < c: return False
count[x + j] -= c
return Truefunction isPossibleDivide(nums, k) {
if (nums.length % k) return false;
const count = new Map();
for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
const keys = [...count.keys()].sort((a, b) => a - b);
for (const x of keys) {
const c = count.get(x);
if (c === 0) continue;
for (let j = 0; j < k; j++) {
if ((count.get(x + j) || 0) < c) return false;
count.set(x + j, count.get(x + j) - c);
}
}
return true;
}class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
if (nums.length % k != 0) return false;
TreeMap<Integer, Integer> count = new TreeMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum);
while (!count.isEmpty()) {
int x = count.firstKey();
int c = count.get(x);
for (int j = 0; j < k; j++) {
int v = count.getOrDefault(x + j, 0);
if (v < c) return false;
if (v == c) count.remove(x + j);
else count.put(x + j, v - c);
}
}
return true;
}
}bool isPossibleDivide(vector<int>& nums, int k) {
if ((int)nums.size() % k) return false;
map<int, int> count;
for (int x : nums) count[x]++;
while (!count.empty()) {
int x = count.begin()->first;
int c = count.begin()->second;
for (int j = 0; j < k; j++) {
if (count[x + j] < c) return false;
count[x + j] -= c;
if (count[x + j] == 0) count.erase(x + j);
}
}
return true;
}Explanation
We want to split the numbers into groups of k consecutive values like [3,4,5,6]. The greedy key is that the smallest remaining number has no choice — it must be the start of a group, because nothing smaller exists to lead a run containing it.
First a quick check: if the array length is not divisible by k, it can never split evenly, so return False. Then we tally every value with a Counter.
We process values in sorted order. For the smallest leftover value x with c copies, we must form c groups all starting at x, so we need at least c copies of each of x, x+1, ..., x+k-1. If any of those is short (count[x+j] < c) we fail; otherwise we subtract c from each.
This is greedy-safe because x can only ever be a group's leader, so consuming it together with the next k-1 values is the only valid move.
Example: nums=[1,2,3,3,4,4,5,6], k=4. Smallest is 1 (one copy), so take 1,2,3,4; the leftovers 3,4,5,6 form the second group. Everything is used, so the answer is true.