Minimum Incompatibility
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 _theminimum 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.
Examples
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 <= 16nums.lengthis divisible byk1 <= nums[i] <= nums.length
Solution
Method 1 – Bitmask Dynamic Programming
Intuition
Since the array is small (n <= 16), we can use bitmask DP to try all possible ways to split the array into k groups of equal size, ensuring no duplicates in any group. For each valid group, we precompute its incompatibility and use DP to find the minimum sum.
Approach
- Calculate the size of each group:
group_size = n // k. - Precompute incompatibility for all valid subsets of size
group_size(no duplicates). - Use DP where
dp[mask]is the minimum incompatibility for the subset of elements represented bymask. - For each mask, try adding a valid group and update the DP value.
- If it's impossible to split, return -1.
Code
C++
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
int n = nums.size(), m = n / k;
int inf = 1e9;
vector<int> inc(1 << n, -1);
for (int mask = 0; mask < (1 << n); ++mask) {
if (__builtin_popcount(mask) != m) continue;
set<int> s;
int mx = 0, mn = 20;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
if (s.count(nums[i])) { mx = -1; break; }
s.insert(nums[i]);
mx = max(mx, nums[i]);
mn = min(mn, nums[i]);
}
}
if (mx != -1) inc[mask] = mx - mn;
}
vector<int> dp(1 << n, inf);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
if (dp[mask] == inf) continue;
vector<int> unused;
for (int i = 0; i < n; ++i) if (!(mask & (1 << i))) unused.push_back(i);
if (unused.size() < m) continue;
int sub = 0;
function<void(int,int,int)> gen = [&](int idx, int cnt, int cur) {
if (cnt == m) {
if (inc[cur] != -1) dp[mask | cur] = min(dp[mask | cur], dp[mask] + inc[cur]);
return;
}
for (int j = idx; j < unused.size(); ++j) gen(j+1, cnt+1, cur | (1 << unused[j]));
};
gen(0,0,0);
}
return dp[(1<<n)-1] == inf ? -1 : dp[(1<<n)-1];
}
};
Go
func minimumIncompatibility(nums []int, k int) int {
n := len(nums)
m := n / k
const inf = 1e9
// Precompute incompatibility for all valid subsets
inc := make(map[int]int)
for mask := 0; mask < (1 << n); mask++ {
if bits.OnesCount(uint(mask)) != m {
continue
}
seen := make(map[int]bool)
values := []int{}
valid := true
for i := 0; i < n; i++ {
if mask&(1<<i) != 0 {
if seen[nums[i]] {
valid = false
break
}
seen[nums[i]] = true
values = append(values, nums[i])
}
}
if valid {
minVal, maxVal := values[0], values[0]
for _, val := range values {
if val < minVal {
minVal = val
}
if val > maxVal {
maxVal = val
}
}
inc[mask] = maxVal - minVal
}
}
// DP to find minimum sum
dp := make([]int, 1<<n)
for i := range dp {
dp[i] = inf
}
dp[0] = 0
for mask := 0; mask < (1 << n); mask++ {
if dp[mask] == inf {
continue
}
// Find unused indices
unused := []int{}
for i := 0; i < n; i++ {
if mask&(1<<i) == 0 {
unused = append(unused, i)
}
}
if len(unused) < m {
continue
}
// Generate all combinations of size m from unused
var generate func(int, int, int)
generate = func(idx, cnt, cur int) {
if cnt == m {
if incomp, exists := inc[cur]; exists {
newMask := mask | cur
if dp[mask]+incomp < dp[newMask] {
dp[newMask] = dp[mask] + incomp
}
}
return
}
for j := idx; j < len(unused); j++ {
generate(j+1, cnt+1, cur|(1<<unused[j]))
}
}
generate(0, 0, 0)
}
if dp[(1<<n)-1] == inf {
return -1
}
return dp[(1<<n)-1]
}
Java
class Solution {
public int minimumIncompatibility(int[] nums, int k) {
int n = nums.length, m = n / k, inf = (int)1e9;
int[] inc = new int[1 << n];
Arrays.fill(inc, -1);
for (int mask = 0; mask < (1 << n); mask++) {
if (Integer.bitCount(mask) != m) continue;
Set<Integer> s = new HashSet<>();
int mx = 0, mn = 20;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
if (s.contains(nums[i])) { mx = -1; break; }
s.add(nums[i]);
mx = Math.max(mx, nums[i]);
mn = Math.min(mn, nums[i]);
}
}
if (mx != -1) inc[mask] = mx - mn;
}
int[] dp = new int[1 << n];
Arrays.fill(dp, inf);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == inf) continue;
List<Integer> unused = new ArrayList<>();
for (int i = 0; i < n; i++) if ((mask & (1 << i)) == 0) unused.add(i);
if (unused.size() < m) continue;
gen(unused, 0, 0, m, mask, dp, inc);
}
return dp[(1<<n)-1] == inf ? -1 : dp[(1<<n)-1];
}
private void gen(List<Integer> unused, int idx, int cnt, int cur, int mask, int[] dp, int[] inc) {
int n = unused.size();
int m = Integer.bitCount(cur);
if (m == unused.size() / (unused.size() / cnt)) {
if (inc[cur] != -1) dp[mask | cur] = Math.min(dp[mask | cur], dp[mask] + inc[cur]);
return;
}
for (int j = idx; j < n; j++) gen(unused, j+1, cnt+1, cur | (1 << unused.get(j)), mask, dp, inc);
}
}
Kotlin
class Solution {
fun minimumIncompatibility(nums: IntArray, k: Int): Int {
val n = nums.size
val m = n / k
val inf = 1_000_000_000
// Precompute incompatibility for all valid subsets
val inc = mutableMapOf<Int, Int>()
for (mask in 0 until (1 shl n)) {
if (Integer.bitCount(mask) != m) continue
val seen = mutableSetOf<Int>()
val values = mutableListOf<Int>()
var valid = true
for (i in 0 until n) {
if (mask and (1 shl i) != 0) {
if (nums[i] in seen) {
valid = false
break
}
seen.add(nums[i])
values.add(nums[i])
}
}
if (valid) {
inc[mask] = values.maxOrNull()!! - values.minOrNull()!!
}
}
// DP to find minimum sum
val dp = IntArray(1 shl n) { inf }
dp[0] = 0
for (mask in 0 until (1 shl n)) {
if (dp[mask] == inf) continue
// Find unused indices
val unused = mutableListOf<Int>()
for (i in 0 until n) {
if (mask and (1 shl i) == 0) {
unused.add(i)
}
}
if (unused.size < m) continue
// Generate all combinations of size m from unused
fun generate(idx: Int, cnt: Int, cur: Int) {
if (cnt == m) {
inc[cur]?.let { incomp ->
val newMask = mask or cur
dp[newMask] = minOf(dp[newMask], dp[mask] + incomp)
}
return
}
for (j in idx until unused.size) {
generate(j + 1, cnt + 1, cur or (1 shl unused[j]))
}
}
generate(0, 0, 0)
}
return if (dp[(1 shl n) - 1] == inf) -1 else dp[(1 shl n) - 1]
}
}
Python
def minimum_incompatibility(nums: list[int], k: int) -> int:
from itertools import combinations
n, m = len(nums), len(nums) // k
inf = float('inf')
inc = {}
for comb in combinations(range(n), m):
vals = [nums[i] for i in comb]
if len(set(vals)) < m: continue
mask = sum(1 << i for i in comb)
inc[mask] = max(vals) - min(vals)
dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == inf: continue
unused = [i for i in range(n) if not (mask & (1 << i))]
if len(unused) < m: continue
for comb in combinations(unused, m):
submask = sum(1 << i for i in comb)
if submask in inc:
##### Rust
```rust
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn minimum_incompatibility(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let m = n / k as usize;
let inf = 1_000_000_000;
// Precompute incompatibility for all valid subsets
let mut inc = HashMap::new();
for mask in 0..(1 << n) {
if mask.count_ones() as usize != m {
continue;
}
let mut seen = HashSet::new();
let mut values = Vec::new();
let mut valid = true;
for i in 0..n {
if mask & (1 << i) != 0 {
if seen.contains(&nums[i]) {
valid = false;
break;
}
seen.insert(nums[i]);
values.push(nums[i]);
}
}
if valid && !values.is_empty() {
let min_val = *values.iter().min().unwrap();
let max_val = *values.iter().max().unwrap();
inc.insert(mask, max_val - min_val);
}
}
// DP to find minimum sum
let mut dp = vec![inf; 1 << n];
dp[0] = 0;
for mask in 0..(1 << n) {
if dp[mask] == inf {
continue;
}
// Find unused indices
let mut unused = Vec::new();
for i in 0..n {
if mask & (1 << i) == 0 {
unused.push(i);
}
}
if unused.len() < m {
continue;
}
// Generate all combinations of size m from unused
fn generate(
idx: usize,
cnt: usize,
cur: usize,
unused: &[usize],
m: usize,
mask: usize,
dp: &mut [i32],
inc: &HashMap<usize, i32>,
) {
if cnt == m {
if let Some(&incomp) = inc.get(&cur) {
let new_mask = mask | cur;
dp[new_mask] = dp[new_mask].min(dp[mask] + incomp);
}
return;
}
for j in idx..unused.len() {
generate(j + 1, cnt + 1, cur | (1 << unused[j]), unused, m, mask, dp, inc);
}
}
generate(0, 0, 0, &unused, m, mask, &mut dp, &inc);
}
if dp[(1 << n) - 1] == inf {
-1
} else {
dp[(1 << n) - 1]
}
}
}
TypeScript
function minimumIncompatibility(nums: number[], k: number): number {
const n = nums.length;
const m = n / k;
const inf = 1_000_000_000;
// Helper function to count set bits
const popcount = (mask: number): number => {
let count = 0;
while (mask) {
count += mask & 1;
mask >>>= 1;
}
return count;
};
// Precompute incompatibility for all valid subsets
const inc = new Map<number, number>();
for (let mask = 0; mask < (1 << n); mask++) {
if (popcount(mask) !== m) continue;
const seen = new Set<number>();
const values: number[] = [];
let valid = true;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
if (seen.has(nums[i])) {
valid = false;
break;
}
seen.add(nums[i]);
values.push(nums[i]);
}
}
if (valid && values.length > 0) {
const minVal = Math.min(...values);
const maxVal = Math.max(...values);
inc.set(mask, maxVal - minVal);
}
}
// DP to find minimum sum
const dp = new Array(1 << n).fill(inf);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask] === inf) continue;
// Find unused indices
const unused: number[] = [];
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) {
unused.push(i);
}
}
if (unused.length < m) continue;
// Generate all combinations of size m from unused
const generate = (idx: number, cnt: number, cur: number): void => {
if (cnt === m) {
const incomp = inc.get(cur);
if (incomp !== undefined) {
const newMask = mask | cur;
dp[newMask] = Math.min(dp[newMask], dp[mask] + incomp);
}
return;
}
for (let j = idx; j < unused.length; j++) {
generate(j + 1, cnt + 1, cur | (1 << unused[j]));
}
};
generate(0, 0, 0);
}
return dp[(1 << n) - 1] === inf ? -1 : dp[(1 << n) - 1];
}
Complexity
- ⏰ Time complexity:
O(n^2 * 2^n), where n is the length of nums. We try all possible subsets and masks. - 🧺 Space complexity:
O(2^n), for DP and incompatibility tables.