Minimum Incompatibility
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 of integers that appear in the array with no particular order.
Example 1
Input
nums = [1,2,1,4], k = 2Output
4The optimal distribution is [1,2] and [1,4], giving incompatibility (2-1) + (4-1) = 4, while [1,1] is invalid because it contains equal elements.
Example 2
Input
nums = [6,3,8,1,3,1,2,2], k = 4Output
6The optimal distribution is [1,2], [2,3], [6,8], and [1,3], giving incompatibility (2-1) + (3-2) + (8-6) + (3-1) = 6.
Constraints
- 1 <= k <= nums.length <= 16
- nums.length is divisible by k
- 1 <= nums[i] <= nums.length
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.