Minimum Incompatibility — Hard Problem & Solution

Distribute nums into k subsets of equal size, where each subset must contain distinct values. A subset's incompatibility is its maximum minus its minimum.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Bit Manipulation, Bitmask
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Distribute nums into k subsets of equal size, where each subset must contain distinct values. A subset's incompatibility is its maximum minus its minimum.

Return the minimum possible sum of the k incompatibilities, or -1 if no such distribution exists.

Example 1

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: `{1,2}` and `{1,4}` give 1 + 3.

Example 2

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: `{1,2}`, `{2,3}`, `{6,8}`, `{1,3}` give 1 + 1 + 2 + 2.

Example 3

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: Four copies of 3 cannot fit into three subsets of size 2.

Constraints

1 <= k <= nums.length <= 12
nums.length % k == 0
1 <= nums[i] <= nums.length

How to solve Minimum Incompatibility

Bitmask DP over the set of placed elements. Precompute each candidate group's incompatibility, then build the partition one group at a time, always anchoring the next group on the lowest unused index so each partition is constructed exactly once.

Approach

For every mask, check that it has size = n / k bits and no repeated value; record max - min.
Set dp[0] = 0; for each reachable mask, take rem = the unused bits and lowBit = its lowest set bit.
Enumerate the submasks of rem that contain lowBit and are valid groups, relaxing dp[mask | sub].
Return dp[full], or -1 if it was never reached.

Why it works

Anchoring on the lowest unused index is what keeps the complexity at O(3ⁿ) rather than O(3ⁿ · k!): without it, the same partition is reached once per ordering of its groups, which is pure waste and can also break the intuition that dp is monotone. The submask enumeration idiom sub = (sub - 1) & rem visits every subset of rem exactly once, and summed over all masks that is the familiar 3ⁿ.

Complexity

Time — O(3ⁿ)
Space — O(2ⁿ)

Pitfalls

Duplicate values inside a group are forbidden, which is the only source of -1.
Groups must all be exactly n / k in size; nothing may be left over.
Enumerating every submask without the lowest-bit anchor multiplies the work by the number of group orderings.

Reference solution

Python

from typing import List

def minimumIncompatibility(nums: List[int], k: int) -> int:
    n = len(nums)
    if n % k != 0:
        return -1
    size = n // k
    full = 1 << n
    INF = 10**9
    cost = [-1] * full
    for mask in range(full):
        vals = [nums[i] for i in range(n) if mask & (1 << i)]
        if len(vals) == size and len(set(vals)) == size:
            cost[mask] = max(vals) - min(vals)
    dp = [INF] * full
    dp[0] = 0
    for mask in range(full):
        if dp[mask] == INF:
            continue
        rem = (full - 1) ^ mask
        if rem == 0:
            continue
        low = rem & -rem
        sub = rem
        while sub:
            if sub & low and cost[sub] >= 0:
                dp[mask | sub] = min(dp[mask | sub], dp[mask] + cost[sub])
            sub = (sub - 1) & rem
    return -1 if dp[full - 1] == INF else dp[full - 1]

JavaScript

var minimumIncompatibility = function(nums, k) {
    var n = nums.length;
    if (n % k !== 0) return -1;
    var size = n / k, full = 1 << n, INF = 1000000000, mask, i;
    var cost = [];
    for (mask = 0; mask < full; mask++) cost.push(-1);
    for (mask = 0; mask < full; mask++) {
        var count = 0, lo = 1000, hi = -1, ok = true;
        var seen = [];
        for (i = 0; i <= n; i++) seen.push(false);
        for (i = 0; i < n; i++) {
            if ((mask & (1 << i)) === 0) continue;
            count++;
            var v = nums[i];
            if (seen[v]) { ok = false; break; }
            seen[v] = true;
            if (v < lo) lo = v;
            if (v > hi) hi = v;
        }
        if (ok && count === size) cost[mask] = hi - lo;
    }
    var dp = [];
    for (mask = 0; mask < full; mask++) dp.push(INF);
    dp[0] = 0;
    for (mask = 0; mask < full; mask++) {
        if (dp[mask] === INF) continue;
        var rem = (full - 1) ^ mask;
        if (rem === 0) continue;
        var lowBit = rem & -rem;
        for (var sub = rem; sub > 0; sub = (sub - 1) & rem) {
            if ((sub & lowBit) === 0) continue;
            if (cost[sub] < 0) continue;
            var cand = dp[mask] + cost[sub];
            if (cand < dp[mask | sub]) dp[mask | sub] = cand;
        }
    }
    return dp[full - 1] === INF ? -1 : dp[full - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue