# Minimum Incompatibility
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-incompatibility)
Canonical: https://scaleengineer.com/dsa/problems/minimum-incompatibility
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## 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 _the **minimum 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.

**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 <= 16`
* `nums.length` is divisible by `k`
* `1 <= nums[i] <= nums.length`

# Approaches
## Brute-Force with Permutations
This approach explores all possible arrangements of the numbers and tries to partition them. It generates every possible permutation of the `nums` array. For each permutation, it divides the array into `k` contiguous subarrays of size `n/k`. Then, it checks if this partitioning is valid (i.e., no subarray has duplicate elements). If it's valid, it calculates the sum of incompatibilities and updates the global minimum.
**Time:** O(n! * n) - There are `n!` permutations to generate (or `n! / (d1! * d2! ...)` for duplicates). For each permutation, we iterate through all `n` elements to check the `k` subsets. This is computationally prohibitive. · **Space:** O(n) - To store a single permutation and for the recursion stack if a recursive permutation generator is used.
**Pros:** Simple to understand the logic.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints (`n` up to 16).
### Explanation
The most straightforward, yet inefficient, way to solve the problem is to try every single possible grouping of numbers. We can model this by generating all permutations of the input array `nums`. For each unique permutation, we can treat it as a fixed ordering and partition it into `k` contiguous segments, each of size `m = nums.length / k`. Each segment is a potential subset. We then validate this partition. A partition is valid if and only if every one of the `k` subsets contains distinct elements. If the partition is valid, we compute the total incompatibility by summing the `max - min` difference for each subset and compare it with the minimum sum found so far. 

```java
// This is a conceptual illustration. A full implementation would require
// a robust permutation generation algorithm, which is omitted for brevity
// as this approach is not feasible for the problem constraints.
class Solution {
    int minIncompatibility = Integer.MAX_VALUE;
    int subsetSize;
    int k;

    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length;
        this.subsetSize = n / k;
        this.k = k;

        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > k) {
                return -1;
            }
        }

        // A real implementation would generate permutations here.
        // For example, using a recursive helper function:
        // generatePermutations(new ArrayList<>(Arrays.stream(nums).boxed()), new ArrayList<>());

        // Due to the massive complexity, this will time out.
        // return minIncompatibility == Integer.MAX_VALUE ? -1 : minIncompatibility;
        return -1; // Placeholder for an infeasible approach
    }

    // Conceptual: checks a single permutation
    private void checkPartition(List<Integer> p) {
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            Set<Integer> subset = new HashSet<>();
            int minVal = Integer.MAX_VALUE;
            int maxVal = Integer.MIN_VALUE;
            boolean duplicates = false;

            for (int j = 0; j < subsetSize; j++) {
                int val = p.get(i * subsetSize + j);
                if (!subset.add(val)) {
                    duplicates = true;
                    break;
                }
                minVal = Math.min(minVal, val);
                maxVal = Math.max(maxVal, val);
            }

            if (duplicates) {
                return; // Invalid partition
            }
            currentSum += maxVal - minVal;
        }
        minIncompatibility = Math.min(minIncompatibility, currentSum);
    }
}
```
### Algorithm
- First, perform a preliminary check. Count the frequency of each number. If any number appears more than `k` times, it's impossible to satisfy the conditions, so return -1.
- Generate all unique permutations of the `nums` array.
- For each permutation:
    - Initialize a flag `isValid` to true and `currentSum` to 0.
    - Divide the permutation into `k` chunks, each of size `m = n/k`.
    - For each chunk (subset):
        - Check for duplicate elements within the chunk. If duplicates exist, set `isValid` to false and break from this inner loop.
        - Find the maximum and minimum elements in the chunk and add their difference to `currentSum`.
    - If `isValid` is still true after checking all chunks, update the global minimum incompatibility with `currentSum`.
- After checking all permutations, if the minimum incompatibility is still at its initial large value, it means no valid distribution was found. Otherwise, return the found minimum.

## Top-Down Dynamic Programming with Memoization
This approach uses recursion with memoization (a form of top-down dynamic programming) to avoid recomputing results for the same subproblems. The state of our recursion is defined by a bitmask, where each bit `i` corresponds to the `i`-th element of the (sorted) `nums` array. A function `solve(mask)` is defined to calculate the minimum incompatibility for the set of elements represented by `mask`.
**Time:** O(2^n * C(n, m)) - In the worst case, for each of the `2^n` states (masks), we might iterate through a significant portion of the `C(n, m)` precomputed subsets. The precomputation itself takes `O(C(n, m) * m)`. This is feasible for small `m` but slow when `m` is close to `n/2`. · **Space:** O(2^n + C(n, m)) - `O(2^n)` for the memoization table and `O(C(n, m))` for storing the precomputed costs, where `C(n, m)` is the number of combinations.
**Pros:** Vastly more efficient than brute force.; Guaranteed to find the optimal solution.; The recursive structure can be intuitive to write based on the problem's recurrence relation.
**Cons:** The time complexity, while much better than brute-force, can still be too high if the number of valid `m`-element subsets (`C(n, m)`) is large.; Requires significant space for the memoization table and precomputed costs.
### Explanation
The core idea is to solve the problem for a set of elements by breaking it down into smaller problems. Let `dp[mask]` be the minimum incompatibility for the elements represented by `mask`. The final answer is `dp[(1<<n)-1]`. 

We can define this with a recurrence. To calculate `dp[mask]`, we can select one valid subset (of size `m`) from it, say `submask`. The value would then be `cost(submask) + dp[mask ^ submask]`. We want the minimum over all possible choices for `submask`.

This can be implemented with a recursive function `solve(mask)` that computes `dp[mask]`. A memoization table stores the results to prevent re-computation.

```java
class Solution {
    private int[] memo;
    private Map<Integer, Integer> costs;
    private int n, m;
    private int[] nums;

    public int minimumIncompatibility(int[] nums, int k) {
        this.n = nums.length;
        this.m = n / k;
        this.nums = nums;

        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > k) return -1;
        }
        Arrays.sort(this.nums);

        this.costs = new HashMap<>();
        // Precompute costs for all valid subsets of size m
        for (int i = 0; i < (1 << n); i++) {
            if (Integer.bitCount(i) == m) {
                Set<Integer> set = new HashSet<>();
                int minIdx = -1, maxIdx = -1;
                boolean valid = true;
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0) {
                        if (!set.add(nums[j])) {
                            valid = false;
                            break;
                        }
                        if (minIdx == -1) minIdx = j;
                        maxIdx = j;
                    }
                }
                if (valid) {
                    costs.put(i, nums[maxIdx] - nums[minIdx]);
                }
            }
        }

        this.memo = new int[1 << n];
        Arrays.fill(memo, -1);

        int result = solve((1 << n) - 1);
        return result >= 1_000_000_000 ? -1 : result;
    }

    private int solve(int mask) {
        if (mask == 0) {
            return 0;
        }
        if (memo[mask] != -1) {
            return memo[mask];
        }

        int res = 1_000_000_000; // Using a large number for infinity
        
        // To avoid permutations of subsets, fix one element to be in the next subset.
        int firstElementIndex = Integer.numberOfTrailingZeros(mask);

        for (Map.Entry<Integer, Integer> entry : costs.entrySet()) {
            int submask = entry.getKey();
            // Ensure submask is a subset of mask and contains the fixed element
            if ((mask & submask) == submask && (submask & (1 << firstElementIndex)) != 0) {
                int remainingResult = solve(mask ^ submask);
                if (remainingResult < 1_000_000_000) {
                    res = Math.min(res, entry.getValue() + remainingResult);
                }
            }
        }
        
        return memo[mask] = res;
    }
}
```
### Algorithm
- First, handle the preliminary check: if any number appears more than `k` times, return -1.
- Sort the `nums` array. This helps in easily calculating the incompatibility of a subset.
- Precompute the incompatibilities of all possible valid subsets of size `m = n/k`. A subset is valid if it has no duplicate numbers. Store these in a map `costs`, where the key is the subset's bitmask and the value is its incompatibility.
- Create a memoization table `memo` of size `2^n` to store the results of `solve(mask)`.
- Implement the recursive function `solve(mask)`:
    - **Base Case:** If `mask` is 0 (no elements left), the incompatibility is 0.
    - **Memoization Check:** If `memo[mask]` has been computed, return the stored value.
    - **Recursive Step:** Initialize a result `res` to infinity. Iterate through all precomputed valid subsets (`submask`). If `submask` is a part of the current `mask`, recursively call the function for the remaining elements (`mask ^ submask`) and update the result: `res = min(res, cost(submask) + solve(mask ^ submask))`. To make this efficient, we only need to consider partitions, so we can fix one element of the `mask` and only consider `submasks` that contain it.
- The final answer is the result of `solve((1<<n) - 1)`.

## Optimized Bottom-Up Dynamic Programming
This is the most efficient approach, building upon the DP with bitmasking idea using a bottom-up iterative method. This avoids recursion overhead and allows for a loop structure that is more efficient. The state `dp[mask]` represents the minimum incompatibility sum for the elements in the bitmask `mask`. We build the `dp` table from `dp[0]` up to `dp[(1<<n)-1]`.
**Time:** O(3^n) or O(2^n * C(n, m)). The most optimized version iterates through masks and their submasks, leading to a total complexity of `O(3^n)`. The simpler implementation shown has a complexity of `O(2^n * C(n, m))`. Both are significantly better than brute force and are capable of passing the given constraints. · **Space:** O(2^n + C(n, m)) - `O(2^n)` for the DP table and `O(C(n, m))` for storing the precomputed costs.
**Pros:** Most efficient known algorithm for this problem under the given constraints.; Avoids recursion overhead, which can be slightly faster in practice.; Guaranteed to find the optimal solution.
**Cons:** The logic, especially the state transitions and loop structures, can be complex to grasp and implement correctly.; Still requires `O(2^n)` space, which can be large.
### Explanation
This approach iteratively computes the solution for all possible subsets of `nums`. We maintain a `dp` array where `dp[mask]` stores the minimum total incompatibility for the elements represented by `mask`. The size of the set represented by `mask` must be a multiple of `m` (the subset size) for it to be a valid state in our partitioning process.

The calculation proceeds as follows: we start with `dp[0] = 0`. Then, we iterate through all masks. For each mask `mask` for which we have a valid solution `dp[mask]`, we try to add a new, non-overlapping (disjoint) subset `submask` to it. The result for the new, larger mask `mask | submask` is then updated with `dp[mask] + cost(submask)`. By iterating through all `mask` and all possible `submask` to add, we eventually compute the value for `dp[(1<<n)-1]`, which is our answer.

An even more optimized version of this approach has a time complexity of `O(3^n)` by iterating through masks and their submasks, but the version shown below is more intuitive and often sufficient.

```java
class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length;
        int m = n / k;

        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > k) return -1;
        }
        Arrays.sort(nums);

        Map<Integer, Integer> costs = new HashMap<>();
        for (int i = 0; i < (1 << n); i++) {
            if (Integer.bitCount(i) == m) {
                Set<Integer> set = new HashSet<>();
                int minIdx = -1, maxIdx = -1;
                boolean valid = true;
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0) {
                        if (!set.add(nums[j])) {
                            valid = false;
                            break;
                        }
                        if (minIdx == -1) minIdx = j;
                        maxIdx = j;
                    }
                }
                if (valid) {
                    costs.put(i, nums[maxIdx] - nums[minIdx]);
                }
            }
        }

        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == Integer.MAX_VALUE) continue;

            for (Map.Entry<Integer, Integer> entry : costs.entrySet()) {
                int submask = entry.getKey();
                if ((mask & submask) == 0) { // If submask is disjoint from mask
                    int nextMask = mask | submask;
                    dp[nextMask] = Math.min(dp[nextMask], dp[mask] + entry.getValue());
                }
            }
        }

        return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
    }
}
```
### Algorithm
- Perform the same preprocessing as the previous approach: check frequencies, sort `nums`, and precompute the `costs` of all valid `m`-element subsets.
- Initialize a `dp` array of size `2^n` with a large value representing infinity. Set `dp[0] = 0`, as the incompatibility for an empty set is zero.
- Iterate through all masks from `0` to `(1<<n) - 1`.
- For each `mask`, if `dp[mask]` is infinity, it means this state is unreachable, so we skip it.
- If `dp[mask]` is valid, we try to extend this solution by adding another valid `m`-element subset to it.
- We iterate through all precomputed valid subsets (`submask` with its `cost`).
- If `submask` does not overlap with the current `mask` (i.e., `(mask & submask) == 0`), it means we can form a new larger set `new_mask = mask | submask`.
- We update the `dp` value for this new mask: `dp[new_mask] = min(dp[new_mask], dp[mask] + cost)`.
- After the loops complete, `dp[(1<<n) - 1]` will hold the minimum incompatibility for the entire set of numbers.

# Solutions
### CSharp

```csharp
public class Solution { public int MinimumIncompatibility ( int [] nums , int k ) { int n = nums . Length ; int m = n / k ; int [] g = new int [ 1 << n ]; Array . Fill ( g , - 1 ); for ( int i = 1 ; i < 1 << n ; ++ i ) { if ( bitCount ( i ) != m ) { continue ; } HashSet < int > s = new (); int mi = 20 , mx = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if (( i >> j & 1 ) == 1 ) { if ( s . Contains ( nums [ j ])) { break ; } s . Add ( nums [ j ]); mi = Math . Min ( mi , nums [ j ]); mx = Math . Max ( mx , nums [ j ]); } } if ( s . Count == m ) { g [ i ] = mx - mi ; } } int [] f = new int [ 1 << n ]; int inf = 1 << 30 ; Array . Fill ( f , inf ); f [ 0 ] = 0 ; for ( int i = 0 ; i < 1 << n ; ++ i ) { if ( f [ i ] == inf ) { continue ; } HashSet < int > s = new (); int mask = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if (( i >> j & 1 ) == 0 && ! s . Contains ( nums [ j ])) { s . Add ( nums [ j ]); mask |= 1 << j ; } } if ( s . Count < m ) { continue ; } for ( int j = mask ; j > 0 ; j = ( j - 1 ) & mask ) { if ( g [ j ] != - 1 ) { f [ i | j ] = Math . Min ( f [ i | j ], f [ i ] + g [ j ]); } } } return f [( 1 << n ) - 1 ] == inf ? - 1 : f [( 1 << n ) - 1 ]; } private int bitCount ( int x ) { int cnt = 0 ; while ( x > 0 ) { x &= x - 1 ; ++ cnt ; } return cnt ; } }
```

### Java

```java
class Solution {
public
  int minimumIncompatibility(int[] nums, int k) {
    int n = nums.length;
    int m = n / k;
    int[] g = new int[1 << n];
    Arrays.fill(g, -1);
    for (int i = 1; i < 1 << n; ++i) {
      if (Integer.bitCount(i) != m) {
        continue;
      }
      Set<Integer> s = new HashSet<>();
      int mi = 20, mx = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          if (!s.add(nums[j])) {
            break;
          }
          mi = Math.min(mi, nums[j]);
          mx = Math.max(mx, nums[j]);
        }
      }
      if (s.size() == m) {
        g[i] = mx - mi;
      }
    }
    int[] f = new int[1 << n];
    final int inf = 1 << 30;
    Arrays.fill(f, inf);
    f[0] = 0;
    for (int i = 0; i < 1 << n; ++i) {
      if (f[i] == inf) {
        continue;
      }
      Set<Integer> s = new HashSet<>();
      int mask = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 0 && !s.contains(nums[j])) {
          s.add(nums[j]);
          mask |= 1 << j;
        }
      }
      if (s.size() < m) {
        continue;
      }
      for (int j = mask; j > 0; j = (j - 1) & mask) {
        if (g[j] != -1) {
          f[i | j] = Math.min(f[i | j], f[i] + g[j]);
        }
      }
    }
    return f[(1 << n) - 1] == inf ? -1 : f[(1 << n) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumIncompatibility(vector<int> &nums, int k) {
    int n = nums.size();
    int m = n / k;
    int g[1 << n];
    memset(g, -1, sizeof(g));
    for (int i = 1; i < 1 << n; ++i) {
      if (__builtin_popcount(i) != m) {
        continue;
      }
      unordered_set<int> s;
      int mi = 20, mx = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          if (s.count(nums[j])) {
            break;
          }
          s.insert(nums[j]);
          mi = min(mi, nums[j]);
          mx = max(mx, nums[j]);
        }
      }
      if (s.size() == m) {
        g[i] = mx - mi;
      }
    }
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < 1 << n; ++i) {
      if (f[i] == 0x3f3f3f3f) {
        continue;
      }
      unordered_set<int> s;
      int mask = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 0 && !s.count(nums[j])) {
          s.insert(nums[j]);
          mask |= 1 << j;
        }
      }
      if (s.size() < m) {
        continue;
      }
      for (int j = mask; j; j = (j - 1) & mask) {
        if (g[j] != -1) {
          f[i | j] = min(f[i | j], f[i] + g[j]);
        }
      }
    }
    return f[(1 << n) - 1] == 0x3f3f3f3f ? -1 : f[(1 << n) - 1];
  }
};

```

### Python

```python
class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int: n = len(nums) m = n // k g = [- 1] * (1 << n) for i in range(1, 1 << n): if i . bit_count() != m: continue s = set() mi, mx = 20, 0 for j, x in enumerate(nums): if i >> j & 1: if x in s: break s . add(x) mi = min(mi, x) mx = max(mx, x) if len(s) == m: g[i] = mx - mi f = [inf] * (1 << n) f[0] = 0 for i in range(1 << n): if f[i] == inf: continue s = set() mask = 0 for j, x in enumerate(nums): if (i >> j & 1) == 0 and x not in s: s . add(x) mask |= 1 << j if len(s) < m: continue j = mask while j: if g[j] != - 1: f[i | j] = min(f[i | j], f[i] + g[j]) j = (j - 1) & mask return f[- 1] if f[- 1] != inf else - 1

```