Minimum Incompatibility

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

1
2
3
4
5


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

1
2
3
4


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

1
2
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

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 by mask.
For each mask, try adding a valid group and update the DP value.
If it’s impossible to split, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91


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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


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]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


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]
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


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.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Bitmask Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#