#1681
Minimum Incompatibility
master · 1700 · lc hard +32 · verified · 41.1% accepted · 298 likes · top 21%
Description
You are given an integer array nums and integer k. Partition nums into k equally sized subsets where no subset contains duplicate values. A subset's incompatibility equals its maximum minus its minimum element. Return the minimum sum of incompatibilities, or -1 if a valid partition is impossible.
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.
Code
1
2
3