Problem Description

Given an integer array nums and an integer k, determine if it is possible to divide the array into sets of k consecutive numbers. Each number in nums must be used exactly once in exactly one set, and each set must contain exactly k consecutive numbers (for example, [1,2,3] is valid for k=3). If it is possible to divide the array in such a way, return true; otherwise, return false.

• Each element in nums must be used in exactly one set; no element can be reused.
• All sets must be of size k and consist of consecutive numbers.
• There may be only one valid way to divide the array, or none.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= nums.length

Thought Process

The first instinct might be to try all possible groupings of size k and check if each forms a set of consecutive numbers. However, this brute-force approach is highly inefficient for large arrays, as the number of combinations grows rapidly.

Instead, we can leverage the fact that consecutive sets must start from the smallest available number and include the next k-1 consecutive numbers. This suggests sorting the array and using a frequency map (hash map) to track how many times each number appears.

The idea is to repeatedly form groups starting from the smallest remaining number, reducing the available count for each number used. If at any point we can't form a complete group, we know it's impossible.

Solution Approach

Here's how we can efficiently solve the problem:

1. Check divisibility: If nums.length is not divisible by k, it's impossible to partition the array as required, so return false immediately.
2. Count frequencies: Use a hash map (or dictionary) to count how many times each number appears in nums.
3. Sort unique numbers: Sort the unique numbers in ascending order. This ensures we always try to build sets starting from the smallest available number.
4. Form groups: For each unique number (in sorted order), if its frequency is greater than zero, try to form a group of k consecutive numbers starting from that number. For each number in the group, reduce its frequency by the amount needed. If any number in the group doesn't have enough frequency left, return false.
5. Repeat: Continue this process for all numbers. If all numbers are used up correctly, return true.

Why use a hash map? The hash map allows us to efficiently check and update the frequency of any number in constant time, which is crucial for performance.

Example Walkthrough

Example: nums = [1,2,3,3,4,4,5,6], k = 4

1. Check divisibility: nums.length = 8, which is divisible by k = 4.
2. Frequency map: {1:1, 2:1, 3:2, 4:2, 5:1, 6:1}
3. Sort unique numbers: [1,2,3,4,5,6]
4. First group: Start at 1 (freq=1). Try to form [1,2,3,4]:
   • 1: freq 1 → 0
   • 2: freq 1 → 0
   • 3: freq 2 → 1
   • 4: freq 2 → 1
5. Next group: Next smallest with freq>0 is 3 (freq=1). Try to form [3,4,5,6]:
   • 3: freq 1 → 0
   • 4: freq 1 → 0
   • 5: freq 1 → 0
   • 6: freq 1 → 0
6. All frequencies are now zero. Return true.

Time and Space Complexity

Brute-force approach: Would involve generating all possible groupings, which is factorial in time and not feasible for large arrays.

Optimized approach:

• Time Complexity:
  • Building the frequency map: O(n)
  • Sorting unique numbers: O(m log m), where m is the number of unique numbers (m ≤ n)
  • Forming groups: Each number is processed at most once per occurrence, so O(n)
  • Total: O(n + m log m)
• Space Complexity:
  • Frequency map: O(m)
  • Sorted unique numbers: O(m)
  • Total: O(m)

This makes the solution efficient and scalable for large inputs.

Summary

This problem is elegantly solved by leveraging sorting and a hash map to efficiently form groups of consecutive numbers. By always starting from the smallest available number and checking if a complete group can be formed, we ensure no overlaps or misses. The approach avoids brute-force groupings, instead using frequency counting and greedy grouping, which is both fast and easy to understand. The key insight is to process the array in order and decrement frequencies as groups are formed, ensuring all numbers are used exactly once.

Code Implementation

from collections import Counter

class Solution:
    def isPossibleDivide(self, nums, k):
        if len(nums) % k != 0:
            return False
        count = Counter(nums)
        for num in sorted(count):
            freq = count[num]
            if freq > 0:
                for i in range(k):
                    if count[num + i] < freq:
                        return False
                    count[num + i] -= freq
        return True
      

#include <vector>
#include <map>
#include <algorithm>

class Solution {
public:
    bool isPossibleDivide(std::vector<int>& nums, int k) {
        if (nums.size() % k != 0) return false;
        std::map<int, int> count;
        for (int num : nums) count[num]++;
        for (auto it = count.begin(); it != count.end(); ++it) {
            int num = it->first;
            int freq = it->second;
            if (freq > 0) {
                for (int i = 0; i < k; ++i) {
                    if (count[num + i] < freq) return false;
                    count[num + i] -= freq;
                }
            }
        }
        return true;
    }
};
      

import java.util.*;

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        if (nums.length % k != 0) return false;
        TreeMap<Integer, Integer> count = new TreeMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        for (int num : count.keySet()) {
            int freq = count.get(num);
            if (freq > 0) {
                for (int i = 0; i < k; i++) {
                    int curr = num + i;
                    if (count.getOrDefault(curr, 0) < freq) return false;
                    count.put(curr, count.get(curr) - freq);
                }
            }
        }
        return true;
    }
}
      

var isPossibleDivide = function(nums, k) {
    if (nums.length % k !== 0) return false;
    let count = {};
    for (let num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    let keys = Object.keys(count).map(Number).sort((a, b) => a - b);
    for (let num of keys) {
        let freq = count[num];
        if (freq > 0) {
            for (let i = 0; i < k; i++) {
                let curr = num + i;
                if ((count[curr] || 0) < freq) return false;
                count[curr] -= freq;
            }
        }
    }
    return true;
};