Link: https://leetcode.com/problems/partition-array-into-k-distinct-groups

Đề bài#

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 elements. All elements in each group are distinct. 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 <= 105
  1 <= nums[i] <= 105
  ​​​​​​​1 <= k <= nums.length

Phân tích bài toán#

Bài toán xung quanh số k, và khả năng chia đều vào các nhóm. Ta nên tìm tất cả các trường hợp fail trước.

• Nếu không thể chia chính xác mỗi nhóm đúng k phần từ => sai => early return 1 điều kiện
• Nếu chia hết được k phần tử vào x nhóm. Bởi vì mỗi phần tử trong 1 nhóm phải là duy nhất => Quy về bài toán đếm và chia phần tử.
• Nghĩ ngay đến hashMap đếm tần suất xuất hiện, time-complexity: O(n), space-complexity: O(n)

Final solution#

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var partitionArray = function (nums, k) {
    if (nums.length % k !== 0) {
        return false;
    }
    const numOfGroup = nums.length / k;
    const frequency = {};
    for (let item of nums) {
        if (frequency[item]) {
            frequency[item]++;
        }
        else {
            frequency[item] = 1;
        }
        if (frequency[item] > numOfGroup) {
            return false
        }
    }
    return true;
};