# Divide Array in Sets of K Consecutive Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers)
Canonical: https://scaleengineer.com/dsa/problems/divide-array-in-sets-of-k-consecutive-numbers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Waymo](https://scaleengineer.com/companies/waymo)
---
## Problem
Given an array of integers `nums` and a positive integer `k`, check whether it is possible to divide this array into sets of `k` consecutive numbers.

Return `true` _if it is possible_.Otherwise, return `false`.

**Example 1:**

**Input:** nums = [1,2,3,3,4,4,5,6], k = 4
**Output:** true
**Explanation:** Array can be divided into [1,2,3,4] and [3,4,5,6].

**Example 2:**

**Input:** nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
**Output:** true
**Explanation:** Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

**Example 3:**

**Input:** nums = [1,2,3,4], k = 3
**Output:** false
**Explanation:** Each array should be divided in subarrays of size 3.

**Constraints:**

* `1 <= k <= nums.length <= 105`
* `1 <= nums[i] <= 109`

**Note:** This question is the same as 846: <https://leetcode.com/problems/hand-of-straights/>

# Approaches
## Brute Force with Sorting and Marking
This approach involves sorting the array first to make finding consecutive numbers easier. Then, it repeatedly scans the array to find and form groups of `k` consecutive numbers, marking used elements along the way.
**Time:** O(N^2). Sorting takes O(N log N). The main loop runs N times. Inside, for each of the N/k groups, we might scan a large portion of the array k-1 times. This leads to a complexity that is roughly quadratic. · **Space:** O(N), where N is the number of elements in `nums`. This is for the `used` array. The space for sorting can also be up to O(N) depending on the implementation.
**Pros:** Conceptually simple and easy to understand.; Works for small inputs.
**Cons:** Highly inefficient due to nested loops, leading to a quadratic time complexity.; Will result in a 'Time Limit Exceeded' error on large inputs.
### Explanation
The brute-force method begins by sorting the input array `nums`. This brings numbers that could potentially form a consecutive sequence close to each other. An essential pre-condition is that the array's length must be a multiple of `k`; otherwise, a valid partition is impossible. We use an auxiliary boolean array, `used`, to track which elements have been assigned to a set. We iterate through each element of the sorted array. If an element `nums[i]` hasn't been used, we treat it as the start of a new potential set. We then attempt to find the subsequent `k-1` consecutive integers (`nums[i]+1`, `nums[i]+2`, etc.) by scanning the rest of the array. If we find a required integer that is not yet used, we mark it as used and proceed to look for the next one. If at any point a required integer for a sequence cannot be found, we conclude that a valid partition is not possible and return `false`. If we manage to group all numbers this way, we return `true`.

```java
import java.util.Arrays;

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        int n = nums.length;
        if (n % k != 0) {
            return false;
        }
        Arrays.sort(nums);
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            
            // Start a new group with nums[i]
            used[i] = true;
            int needed = k - 1;
            int lastNum = nums[i];
            
            if (needed > 0) {
                for (int j = i + 1; j < n; j++) {
                    if (!used[j] && nums[j] == lastNum + 1) {
                        used[j] = true;
                        lastNum = nums[j];
                        needed--;
                        if (needed == 0) {
                            break;
                        }
                    }
                }
            }

            if (needed > 0) {
                return false;
            }
        }
        
        return true;
    }
}
```
### Algorithm
*   First, perform a preliminary check: if the length of the array `nums` is not divisible by `k`, it's impossible to partition it, so return `false`.
*   Sort the array `nums` in ascending order.
*   Use a boolean array `used` of the same size as `nums` to keep track of which numbers have already been placed into a group. Initially, all elements are marked as not used.
*   Iterate through the sorted array `nums` from left to right. For each number `nums[i]`:
    *   If `nums[i]` has already been used (i.e., `used[i]` is true), skip it.
    *   If it's not used, we try to form a new group of `k` consecutive numbers starting with `nums[i]`.
    *   We search for the next `k-1` consecutive numbers (`nums[i]+1`, `nums[i]+2`, ..., `nums[i]+k-1`) in the rest of the array.
    *   For each required number, we perform a linear scan from the position `i+1`. If we find the required number `nums[j]` and it hasn't been used yet, we mark it as used (`used[j] = true`) and continue searching for the next number in the sequence.
    *   If any of the `k-1` consecutive numbers cannot be found, it's impossible to form the required groups, so we return `false`.
*   If we successfully iterate through the entire array and group all numbers, return `true`.

## Using a Frequency Map and Sorting
This approach improves upon the brute-force method by using a hash map to store the frequency of each number. This allows for constant-time lookups and updates for the counts of numbers, avoiding the costly linear scans. The array is still sorted to ensure we always start new sequences with the smallest available number.
**Time:** O(N log N). Building the hash map is O(N). Sorting the array is O(N log N). The final iteration processes each number, and the inner loop runs `k` times only for the `N/k` sequence starts. This part takes O(N) time. The sorting step is the bottleneck. · **Space:** O(N) in the worst case for the hash map, if all numbers in the input array are unique.
**Pros:** Much more efficient than the brute-force approach with O(N log N) complexity.; Relatively straightforward to implement.
**Cons:** Sorting the entire input array of N elements can be less efficient than only sorting the unique elements, especially if there are many duplicates.
### Explanation
A more efficient way to solve the problem is to use a hash map to count the occurrences of each number. This avoids the expensive O(N) scans to find numbers for a sequence. The algorithm is as follows:

1.  Perform the initial check: if `nums.length` is not divisible by `k`, return `false`.
2.  Populate a hash map with the frequencies of each number in the `nums` array. This takes O(N) time.
3.  Sort the original `nums` array. This is a key step, as it allows us to process potential sequences in an orderly fashion. By iterating through the sorted array, whenever we encounter a number that can start a sequence, we know it's the smallest possible start for any remaining available numbers.
4.  Iterate through the sorted `nums`. For each number `num`, check its count in the frequency map. If the count is zero, it has already been consumed by a previous sequence, so we skip it. If the count is positive, we treat `num` as the beginning of a new sequence. We then verify that we have enough cards for the entire sequence of `k` (i.e., `num, num+1, ..., num+k-1`) by checking their counts in the map. If any number is missing, we return `false`. Otherwise, we decrement the counts for all `k` numbers in the map and continue.

If we successfully process every number, we return `true`.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        if (nums.length % k != 0) {
            return false;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        Arrays.sort(nums);
        for (int num : nums) {
            if (counts.get(num) == 0) {
                continue;
            }
            for (int i = 0; i < k; i++) {
                int currentNum = num + i;
                if (counts.getOrDefault(currentNum, 0) == 0) {
                    return false;
                }
                counts.put(currentNum, counts.get(currentNum) - 1);
            }
        }
        return true;
    }
}
```
### Algorithm
*   First, check if `nums.length % k != 0`. If so, return `false`.
*   Create a `HashMap<Integer, Integer>` to store the frequency of each number in `nums`.
*   Sort the input array `nums` in ascending order.
*   Iterate through each `num` in the sorted `nums` array:
    *   If the frequency of `num` in the map is 0, it means it has already been used in another sequence, so we `continue`.
    *   If the frequency is greater than 0, `num` must be the start of a new sequence.
    *   For this new sequence, check for the existence of `num, num+1, ..., num+k-1`.
    *   Iterate from `i = 0` to `k-1`. For each `currentNum = num + i`:
        *   If `currentNum` is not in the map or its count is 0, return `false`.
        *   Decrement the count of `currentNum` in the map.
*   If the entire loop completes, it means all numbers have been successfully grouped. Return `true`.

## Optimal Approach with an Ordered Map (TreeMap)
This is the most efficient approach. It uses a `TreeMap` to maintain counts of the numbers in a sorted order of the numbers themselves. This avoids sorting the entire `N`-element input array and instead works with the unique numbers, which can be much fewer, leading to better performance when there are many duplicates.
**Time:** O(N log U), where N is the number of elements and U is the number of unique elements. Building the `TreeMap` takes O(N log U). Processing involves map operations (get, put, remove) which take O(log U) each. Each number is effectively processed a constant number of times, leading to the overall complexity. · **Space:** O(U), where U is the number of unique elements in `nums`. This is for storing the `TreeMap`. In the worst case, U can be N, making the space complexity O(N).
**Pros:** The most time-efficient solution, especially when the number of unique elements `U` is much smaller than `N`.; Avoids sorting the potentially large input array directly.
**Cons:** The logic can be slightly more complex to grasp compared to the hash map + sort approach.; `TreeMap` operations have a logarithmic time cost, though this is what provides the efficiency.
### Explanation
This optimal approach leverages a `TreeMap`, which is a sorted map data structure. It combines the frequency counting and sorting steps efficiently.

1.  As always, we first check if `nums.length` is divisible by `k`.
2.  We populate a `TreeMap` with the numbers from the input array as keys and their frequencies as values. The `TreeMap` automatically maintains the keys in ascending order. This costs O(N log U) time, where U is the number of unique elements.
3.  We then enter a loop that continues as long as the map is not empty.
4.  In each iteration, we retrieve the smallest key (`start`) from the map. This is an O(log U) operation. This `start` number is guaranteed to be the smallest available number that can begin a sequence.
5.  We get its frequency, `count`. This means we must form `count` sequences starting with `start`.
6.  We then check if we can form `count` full sequences. We iterate from `i = 0` to `k-1`, checking if the map contains `start + i` with a frequency of at least `count`. If this condition fails for any number in the sequence, we return `false`.
7.  If all numbers for the `count` sequences are available, we decrement their frequencies in the map by `count`. If a number's frequency drops to zero, we remove it from the map. This removal is crucial for efficiency, as it ensures the next `firstKey()` call correctly gives us the next smallest number that needs to start a sequence.

If the map becomes empty, it means all numbers were successfully partitioned, and we return `true`.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        if (nums.length % k != 0) {
            return false;
        }
        Map<Integer, Integer> counts = new TreeMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        while (!counts.isEmpty()) {
            int start = ((TreeMap<Integer, Integer>) counts).firstKey();
            int count = counts.get(start);
            
            for (int i = 0; i < k; i++) {
                int currentNum = start + i;
                if (counts.getOrDefault(currentNum, 0) < count) {
                    return false;
                }
                counts.put(currentNum, counts.get(currentNum) - count);
                if (counts.get(currentNum) == 0) {
                    counts.remove(currentNum);
                }
            }
        }
        
        return true;
    }
}
```
### Algorithm
*   First, check if `nums.length % k != 0`. If so, return `false`.
*   Create a `TreeMap<Integer, Integer>` to store the frequency of each number. A `TreeMap` automatically keeps the keys (the numbers) in sorted order.
*   While the `TreeMap` is not empty:
    *   Get the smallest key (the first number) from the map, let's call it `start`.
    *   Get its frequency, `count`.
    *   This `start` must begin `count` new sequences.
    *   Iterate from `i = 0` to `k-1`. For each `currentNum = start + i`:
        *   Check if the map has `currentNum` and if its frequency is at least `count`. If not, return `false`.
        *   Update the frequency of `currentNum` by subtracting `count`.
        *   If the new frequency of `currentNum` is 0, remove it from the map. This is a key optimization.
*   If the loop finishes (map becomes empty), return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPossibleDivide(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int v : nums) {
      cnt.put(v, cnt.getOrDefault(v, 0) + 1);
    }
    Arrays.sort(nums);
    for (int v : nums) {
      if (cnt.containsKey(v)) {
        for (int x = v; x < v + k; ++x) {
          if (!cnt.containsKey(x)) {
            return false;
          }
          cnt.put(x, cnt.get(x) - 1);
          if (cnt.get(x) == 0) {
            cnt.remove(x);
          }
        }
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossibleDivide(vector<int> &nums, int k) {
    unordered_map<int, int> cnt;
    for (int &v : nums)
      ++cnt[v];
    sort(nums.begin(), nums.end());
    for (int &v : nums) {
      if (cnt.count(v)) {
        for (int x = v; x < v + k; ++x) {
          if (!cnt.count(x)) {
            return false;
          }
          if (--cnt[x] == 0) {
            cnt.erase(x);
          }
        }
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool: cnt = Counter(nums) for v in sorted(nums): if cnt[v]: for x in range(v, v + k): if cnt[x] == 0: return False cnt[x] -= 1 if cnt[x] == 0: cnt . pop(x) return True

```