Minimum Incompatibility

Hard
1068.

Minimum Incompatibility

Minimum Incompatibility is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumIncompatibility = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Incompatibility — Solution in Python, Java & C++

Minimum Incompatibility solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Incompatibility is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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

Hints for Minimum Incompatibility

  1. Hint 1

    n <= 12 — a bitmask over which elements have been placed.

  2. Hint 2

    Precompute, for every mask of exactly n / k bits with no repeated value, its max - min.

  3. Hint 3

    To avoid counting the same partition in every order, always force the next group to contain the lowest unused index.

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

  1. For every mask, check that it has size = n / k bits and no repeated value; record max - min.
  2. Set dp[0] = 0; for each reachable mask, take rem = the unused bits and lowBit = its lowest set bit.
  3. Enumerate the submasks of rem that contain lowBit and are valid groups, relaxing dp[mask | sub].
  4. 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]

Java

public static int minimumIncompatibility(int[] nums, int k) {
    int n = nums.length;
    if (n % k != 0) return -1;
    int size = n / k;
    int full = 1 << n;
    final int INF = 1000000000;
    int[] cost = new int[full];
    Arrays.fill(cost, -1);
    for (int mask = 0; mask < full; mask++) {
        int count = 0, lo = 1000, hi = -1;
        boolean ok = true;
        boolean[] seen = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            count++;
            int v = nums[i];
            if (seen[v]) {
                ok = false;
                break;
            }
            seen[v] = true;
            lo = Math.min(lo, v);
            hi = Math.max(hi, v);
        }
        if (ok && count == size) cost[mask] = hi - lo;
    }
    int[] dp = new int[full];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == INF) continue;
        int rem = (full - 1) ^ mask;
        if (rem == 0) continue;
        int lowBit = rem & (-rem);
        for (int sub = rem; sub > 0; sub = (sub - 1) & rem) {
            if ((sub & lowBit) == 0) continue;
            if (cost[sub] < 0) continue;
            dp[mask | sub] = Math.min(dp[mask | sub], dp[mask] + cost[sub]);
        }
    }
    return dp[full - 1] == INF ? -1 : dp[full - 1];
}

C++

int minimumIncompatibility(vector<int>& nums, int k) {
    int n = (int) nums.size();
    if (n % k != 0) return -1;
    int size = n / k;
    int full = 1 << n;
    const int INF = 1000000000;
    vector<int> cost(full, -1);
    for (int mask = 0; mask < full; mask++) {
        int count = 0, lo = 1000, hi = -1;
        bool ok = true;
        vector<bool> seen(n + 1, false);
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            count++;
            int v = nums[i];
            if (seen[v]) {
                ok = false;
                break;
            }
            seen[v] = true;
            lo = min(lo, v);
            hi = max(hi, v);
        }
        if (ok && count == size) cost[mask] = hi - lo;
    }
    vector<int> dp(full, INF);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == INF) continue;
        int rem = (full - 1) ^ mask;
        if (rem == 0) continue;
        int lowBit = rem & (-rem);
        for (int sub = rem; sub > 0; sub = (sub - 1) & rem) {
            if ((sub & lowBit) == 0) continue;
            if (cost[sub] < 0) continue;
            dp[mask | sub] = min(dp[mask | sub], dp[mask] + cost[sub]);
        }
    }
    return dp[full - 1] == INF ? -1 : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming