Problem Explanation

The problem asks whether it is possible to divide an array of integers into distinct groups of K consecutive numbers. The rules state that the integers may repeat, and the order in which they appear in the array is irrelevant.

For instance, given the array [1,2,3,3,4,4,5,6] with k=4, the array can be divided into two sets [1,2,3,4] and [3,4,5,6], both of length 4 with consecutive numbers, so the output should be true.

Approach

The solution uses a map to keep track of each integer in the array and its respective count. It then iterates over the map. From the current key, it tries to remove k consecutive elements from the map. If at any point it's not possible to remove an element, it means it's not possible to form a group of k consecutive numbers and the function will return false. If it's able to remove k elements for every key in the map, it means it's possible to divide the array into sets of k consecutive numbers and hence returns true.

Step by step example

Let's illustrate this with the following example: nums = [1,2,3,3,4,4,5,6], k=4. The map will be:

1:1 2:2 3:2 4:2 5:1 6:1

We iterate from the first entry of the map (1,1):

• We remove 1 1, 1 2, 1 3 and 1 4. The map becomes

  1:0 2:1 3:1 4:1 5:1 6:1

The next entry has a count of 0, so we skip it and move to the next one (2,1):

• We remove 1 2, 1 3, 1 4 and 1 5. The map is now:

  1:0 2:0 3:0 4:0 5:0 6:1

We keep iterating until we remove 1 6 and exhaust all elements in the map. We return true because we were able to successfully form groups of k consecutive numbers.

Solution

Python

1
2python
3from collections import Counter
4class Solution:
5    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
6        # create a frequency counter of the numbers
7        count = Counter(nums)
8        # iterate over the sorted keys
9        for num in sorted(count):
10            occurence = count[num]
11            if occurence > 0: # we only consider numbers that appear more than 0 times
12                # we try to remove k consecutive numbers
13                for i in range(num, num + k):
14                    if count[i] < occurence:
15                        return False
16                    count[i] -= occurence
17        return True

Java

1
2java
3class Solution {
4    public boolean isPossibleDivide(int[] nums, int k) {
5        if(nums.length % k != 0) return false;
6
7        TreeMap<Integer, Integer> count = new TreeMap<>();
8
9        for(int num : nums)
10            count.put(num, count.getOrDefault(num, 0) + 1);
11
12        while(count.size() > 0) {
13            int first = count.firstKey();
14            for(int i = 0; i < k; ++i) {
15                if(!count.containsKey(first + i))
16                    return false;
17                
18                int c = count.get(first + i);
19                if(c == 1)
20                    count.remove(first + i);
21                else
22                    count.put(first + i, c - 1);
23            }
24        }
25
26        return true;
27    }
28}

Javascript

1
2javascript
3var isPossibleDivide = function(nums, k) {
4    let count = {}, keys;
5    for(let num of nums)
6        count[num] =-~count[num];
7    
8    keys = Object.keys(count).sort((a, b) => a - b);
9    
10    for(let key of keys){
11        while (count[key] > 0){
12            for(let i = k; i--; --count[key + i]);
13            if (count[key + i] < 0) return false;
14        }
15    }
16    return true;
17};

C++

1
2cpp
3class Solution {
4public:
5    bool isPossibleDivide(vector<int>& nums, int k) {
6        map<int, int> count;
7
8        for (const int num : nums)
9            ++count[num];
10
11        for (const auto& [start, _] : count) {
12            const int value = count[start];
13            if (value > 0)
14                for (int i = start; i < start + k; ++i) {
15                    count[i] -= value;
16                    if (count[i] < 0)
17                        return false;
18                }
19        }
20
21        return true;
22    }
23};

C#

1
2csharp
3public class Solution {
4    public bool IsPossibleDivide(int[] nums, int k) {
5        if(nums.Length % k != 0) return false;
6        
7        SortedDictionary<int, int> counts = new SortedDictionary<int, int>();
8        
9        foreach(int num in nums){
10            if(!counts.ContainsKey(num)){
11                counts.Add(num, 1);
12            }
13            else{
14                counts[num] += 1;
15            }
16        }
17
18        foreach(KeyValuePair<int, int> kvp in counts){
19            while(counts[kvp.Key] > 0){
20                for(int i=k-1; i >= 0; i--){
21                    if(counts.ContainsKey(kvp.Key + i)){
22                        counts[kvp.Key + i]--;
23                        if(counts[kvp.Key + i] == 0) counts.Remove(kvp.Key + i);
24                    }
25                    else{
26                        return false;
27                    }
28                }
29            }
30        }
31        
32        return counts.Count == 0;
33    }
34}

Given the above solutions, the problem can be efficiently solved in many programming languages like Python, Java, JavaScript, C++, and C#. They all use a similar approach where a map or counter is used to keep the frequency of each element in the given array. Then we iterate these counts in a sorted manner.

For each number, we check if we can form a group of K consecutive numbers by subtracting the occurrences of K consecutive numbers from the count. If the count of any number in the range from the number to number + K (exclusive) is less than the occurrence of the number, we return false indicating that it's impossible to divide the array into distinct groups of K consecutive numbers.

If we have successfully iterated through all the numbers in the counter without returning false, we return true to indicate that we can divide the array into sets of K consecutive numbers.

These solutions all have a time complexity of O(NlogN) because of sorting the keys of the counter. They also have a space complexity of O(N) for storing the counter, where N is the length of the input array.

These solutions provide a good balance between simplicity and efficiency. They are implementation-friendly and don't require deep programming or algorithmic knowledge.