Minimum Incompatibility
HardPrompt
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 <= 16nums.lengthis divisible byk1 <= nums[i] <= nums.length
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- First, perform a preliminary check. Count the frequency of each number. If any number appears more than
ktimes, it's impossible to satisfy the conditions, so return -1. - Generate all unique permutations of the
numsarray. - For each permutation:
- Initialize a flag
isValidto true andcurrentSumto 0. - Divide the permutation into
kchunks, each of sizem = n/k. - For each chunk (subset):
- Check for duplicate elements within the chunk. If duplicates exist, set
isValidto false and break from this inner loop. - Find the maximum and minimum elements in the chunk and add their difference to
currentSum.
- Check for duplicate elements within the chunk. If duplicates exist, set
- If
isValidis still true after checking all chunks, update the global minimum incompatibility withcurrentSum.
- Initialize a flag
- 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.
Walkthrough
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.
// 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); }}Complexity
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.
Trade-offs
Pros
Simple to understand the logic.
Cons
Extremely high time complexity, making it infeasible for the given constraints (
nup to 16).
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.
Algorithm
- First, handle the preliminary check: if any number appears more than
ktimes, return -1. - Sort the
numsarray. 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 mapcosts, where the key is the subset's bitmask and the value is its incompatibility. - Create a memoization table
memoof size2^nto store the results ofsolve(mask). - Implement the recursive function
solve(mask):- Base Case: If
maskis 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
resto infinity. Iterate through all precomputed valid subsets (submask). Ifsubmaskis a part of the currentmask, 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 themaskand only considersubmasksthat contain it.
- Base Case: If
- The final answer is the result of
solve((1<<n) - 1).
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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].
Algorithm
- Perform the same preprocessing as the previous approach: check frequencies, sort
nums, and precompute thecostsof all validm-element subsets. - Initialize a
dparray of size2^nwith a large value representing infinity. Setdp[0] = 0, as the incompatibility for an empty set is zero. - Iterate through all masks from
0to(1<<n) - 1. - For each
mask, ifdp[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 validm-element subset to it. - We iterate through all precomputed valid subsets (
submaskwith itscost). - If
submaskdoes not overlap with the currentmask(i.e.,(mask & submask) == 0), it means we can form a new larger setnew_mask = mask | submask. - We update the
dpvalue 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.
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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]; }}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]; }};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 - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.