1681. Minimum Incompatibility

Description

You are given an integer array nums​​​ and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset's incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

 

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.

 

Constraints:

• 1 <= k <= nums.length <= 16
• nums.length is divisible by k
• 1 <= nums[i] <= nums.length

 

Solutions

Solution: Dynamic Programming + Bit Manipulation

• Time complexity: O(2ⁿ*n)
• Space complexity: O(2ⁿ)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumIncompatibility = function (nums, k) {
  const n = nums.length;
  const totalMask = 1 << n;
  const subsetSize = n / k;
  const subsetMap = new Map();
  const dp = Array.from({ length: totalMask }, () => -1);

  const isValidSubsetSize = mask => {
    let count = 0;

    while (mask) {
      count += mask & 1;

      if (count > subsetSize) return false;

      mask >>= 1;
    }

    return count === subsetSize;
  };

  const getIncompatibility = mask => {
    if (!isValidSubsetSize(mask)) return -1;
    const visited = new Set();
    let min = Number.MAX_SAFE_INTEGER;
    let max = 0;

    for (let index = 0; index < n; index++) {
      if ((mask & (1 << index)) === 0) continue;
      const num = nums[index];

      if (visited.has(num)) return -1;

      visited.add(num);
      min = Math.min(num, min);
      max = Math.max(num, max);
    }

    return max - min;
  };

  for (let mask = 0; mask < totalMask; mask++) {
    const incompatibility = getIncompatibility(mask);

    if (incompatibility === -1) continue;

    subsetMap.set(mask, incompatibility);
  }

  const distributeSubset = mask => {
    if (mask === totalMask - 1) return 0;
    if (dp[mask] !== -1) return dp[mask];
    let result = Number.MAX_SAFE_INTEGER;

    for (const [subset, incompatibility] of subsetMap) {
      if (subset & mask) continue;
      const sum = incompatibility + distributeSubset(mask | subset);

      result = Math.min(sum, result);
    }

    dp[mask] = result;

    return result;
  };

  const result = distributeSubset(0);

  return result === Number.MAX_SAFE_INTEGER ? -1 : result;
};