3659. Partition Array Into K-Distinct Groups

Description

You are given an integer array nums and an integer k.

Your task is to determine whether it is possible to partition all elements of nums into one or more groups such that:

Each group contains exactly k distinct elements.
Each element in nums must be assigned to exactly one group.

Return true if such a partition is possible, otherwise return false.

Example 1:

Input: nums = [1,2,3,4], k = 2

Output: true

Explanation:

One possible partition is to have 2 groups:

Group 1: [1, 2]
Group 2: [3, 4]

Each group contains k = 2 distinct elements, and all elements are used exactly once.

Example 2:

Input: nums = [3,5,2,2], k = 2

Output: true

Explanation:

One possible partition is to have 2 groups:

Group 1: [2, 3]
Group 2: [2, 5]

Each group contains k = 2 distinct elements, and all elements are used exactly once.

Example 3:

Input: nums = [1,5,2,3], k = 3

Output: false

Explanation:

We cannot form groups of k = 3 distinct elements using all values exactly once.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= nums.length

Solutions

Solution 1: Counting

We denote the length of the array as \(n\). If \(n\) is not divisible by \(k\), then we cannot partition the array into groups where each group contains \(k\) elements, so we directly return \(\text{false}\).

Next, we calculate the size of each group \(m = n / k\) and count the occurrence of each element in the array. If the occurrence count of any element exceeds \(m\), then it cannot be distributed to any group, so we directly return \(\text{false}\).

Finally, if the occurrence count of all elements does not exceed \(m\), then we can partition the array into groups where each group contains \(k\) elements, and we return \(\text{true}\).

Time complexity \(O(n)\), space complexity \(O(n)\) or \(O(M)\). Where \(n\) is the length of the array, and \(M\) is the maximum value of elements in the array.

Python3JavaC++GoTypeScript

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> bool:
        m, mod = divmod(len(nums), k)
        if mod:
            return False
        return max(Counter(nums).values()) <= m

class Solution {
    public boolean partitionArray(int[] nums, int k) {
        int n = nums.length;
        if (n % k != 0) {
            return false;
        }
        int m = n / k;
        int mx = Arrays.stream(nums).max().getAsInt();
        int[] cnt = new int[mx + 1];
        for (int x : nums) {
            if (++cnt[x] > m) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool partitionArray(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k) {
            return false;
        }
        int m = n / k;
        int mx = *ranges::max_element(nums);
        vector<int> cnt(mx + 1);
        for (int x : nums) {
            if (++cnt[x] > m) {
                return false;
            }
        }
        return true;
    }
};

func partitionArray(nums []int, k int) bool {
    n := len(nums)
    if n%k != 0 {
        return false
    }
    m := n / k
    mx := slices.Max(nums)
    cnt := make([]int, mx+1)
    for _, x := range nums {
        if cnt[x]++; cnt[x] > m {
            return false
        }
    }
    return true
}

function partitionArray(nums: number[], k: number): boolean {
    const n = nums.length;
    if (n % k) {
        return false;
    }
    const m = n / k;
    const mx = Math.max(...nums);
    const cnt: number[] = Array(mx + 1).fill(0);
    for (const x of nums) {
        if (++cnt[x] > m) {
            return false;
        }
    }
    return true;
}

3659. Partition Array Into K-Distinct Groups

Description

Solutions

Solution 1: Counting

Comments