1296. Divide Array in Sets of K Consecutive Numbers

Description

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 <= 10⁵
1 <= nums[i] <= 10⁹

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

Solutions

Solution 1: Hash Table + Sorting

First, we check if the length of the array \(\textit{nums}\) is divisible by \(\textit{k}\). If it is not divisible, it means the array cannot be divided into subarrays of length \(\textit{k}\), and we return \(\text{false}\) directly.

Next, we use a hash table \(\textit{cnt}\) to count the occurrences of each number in the array \(\textit{nums}\), and then we sort the array \(\textit{nums}\).

After sorting, we iterate through the array \(\textit{nums}\), and for each number \(x\), if \(\textit{cnt}[x]\) is not \(0\), we enumerate each number \(y\) from \(x\) to \(x + \textit{k} - 1\). If \(\textit{cnt}[y]\) is \(0\), it means we cannot divide the array into subarrays of length \(\textit{k}\), and we return \(\text{false}\) directly. Otherwise, we decrement \(\textit{cnt}[y]\) by \(1\).

After the loop, if no issues were encountered, it means we can divide the array into subarrays of length \(\textit{k}\), and we return \(\text{true}\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScript

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

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        if (nums.length % k != 0) {
            return false;
        }
        Arrays.sort(nums);
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        for (int x : nums) {
            if (cnt.getOrDefault(x, 0) > 0) {
                for (int y = x; y < x + k; ++y) {
                    if (cnt.merge(y, -1, Integer::sum) < 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        if (nums.size() % k) {
            return false;
        }
        ranges::sort(nums);
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }
        for (int x : nums) {
            if (cnt.contains(x)) {
                for (int y = x; y < x + k; ++y) {
                    if (!cnt.contains(y)) {
                        return false;
                    }
                    if (--cnt[y] == 0) {
                        cnt.erase(y);
                    }
                }
            }
        }
        return true;
    }
};

func isPossibleDivide(nums []int, k int) bool {
    if len(nums)%k != 0 {
        return false
    }
    sort.Ints(nums)
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for _, x := range nums {
        if cnt[x] > 0 {
            for y := x; y < x+k; y++ {
                if cnt[y] == 0 {
                    return false
                }
                cnt[y]--
            }
        }
    }
    return true
}

function isPossibleDivide(nums: number[], k: number): boolean {
    if (nums.length % k !== 0) {
        return false;
    }
    const cnt = new Map<number, number>();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    nums.sort((a, b) => a - b);
    for (const x of nums) {
        if (cnt.get(x)! > 0) {
            for (let y = x; y < x + k; y++) {
                if ((cnt.get(y) || 0) === 0) {
                    return false;
                }
                cnt.set(y, cnt.get(y)! - 1);
            }
        }
    }
    return true;
}

Solution 2: Ordered Set

Similar to Solution 1, we first check if the length of the array \(\textit{nums}\) is divisible by \(\textit{k}\). If it is not divisible, it means the array cannot be divided into subarrays of length \(\textit{k}\), and we return \(\text{false}\) directly.

Next, we use an ordered set \(\textit{sd}\) to count the occurrences of each number in the array \(\textit{nums}\).

Then, we repeatedly extract the smallest value \(x\) from the ordered set and enumerate each number \(y\) from \(x\) to \(x + \textit{k} - 1\). If these numbers all appear in the ordered set with non-zero occurrences, we decrement their occurrence count by \(1\). If the occurrence count becomes \(0\) after the decrement, we remove the number from the ordered set; otherwise, it means we cannot divide the array into subarrays of length \(\textit{k}\), and we return \(\text{false}\).

If we can successfully divide the array into subarrays of length \(\textit{k}\), we return \(\text{true}\) after completing the traversal.