1681. Minimum Incompatibility - Leetcode Solution

Code Implementation

from typing import List
import math

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        from collections import Counter
        n = len(nums)
        group_size = n // k
        count = Counter(nums)
        if any(v > k for v in count.values()):
            return -1

        # Precompute all valid groups (subsets of size group_size with unique elements)
        all_masks = []
        for mask in range(1 << n):
            if bin(mask).count('1') == group_size:
                seen = set()
                valid = True
                vals = []
                for i in range(n):
                    if (mask & (1 << i)):
                        if nums[i] in seen:
                            valid = False
                            break
                        seen.add(nums[i])
                        vals.append(nums[i])
                if valid:
                    incompat = max(vals) - min(vals)
                    all_masks.append((mask, incompat))

        # DP: dp[mask] = min incompatibility for used elements = mask
        dp = [math.inf] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            if dp[mask] == math.inf:
                continue
            unused = ((1 << n) - 1) ^ mask
            sub = unused
            while sub:
                if bin(sub).count('1') == group_size:
                    # Is this sub a valid group?
                    for group_mask, incompat in all_masks:
                        if group_mask == sub:
                            new_mask = mask | group_mask
                            dp[new_mask] = min(dp[new_mask], dp[mask] + incompat)
                            break
                sub = (sub - 1) & unused
        return dp[(1 << n) - 1] if dp[(1 << n) - 1] < math.inf else -1

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        int group_size = n / k;
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;
        for (auto &it : freq) if (it.second > k) return -1;

        vector<pair<int, int>> valid_masks;
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (__builtin_popcount(mask) != group_size) continue;
            vector<int> vals;
            unordered_map<int, int> seen;
            bool valid = true;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    if (++seen[nums[i]] > 1) { valid = false; break; }
                    vals.push_back(nums[i]);
                }
            }
            if (valid) {
                int incompat = *max_element(vals.begin(), vals.end()) - *min_element(vals.begin(), vals.end());
                valid_masks.push_back({mask, incompat});
            }
        }

        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] == INT_MAX) continue;
            int unused = ((1 << n) - 1) ^ mask;
            for (auto &p : valid_masks) {
                int group_mask = p.first, incompat = p.second;
                if ((group_mask & mask) == 0) {
                    int new_mask = mask | group_mask;
                    dp[new_mask] = min(dp[new_mask], dp[mask] + incompat);
                }
            }
        }
        return dp[(1 << n) - 1] == INT_MAX ? -1 : dp[(1 << n) - 1];
    }
};

import java.util.*;

class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length, groupSize = n / k;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
        for (int v : freq.values()) if (v > k) return -1;

        List<int[]> validMasks = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            if (Integer.bitCount(mask) != groupSize) continue;
            Set<Integer> seen = new HashSet<>();
            List<Integer> vals = new ArrayList<>();
            boolean valid = true;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    if (!seen.add(nums[i])) { valid = false; break; }
                    vals.add(nums[i]);
                }
            }
            if (valid) {
                int min = Collections.min(vals), max = Collections.max(vals);
                validMasks.add(new int[]{mask, max - min});
            }
        }

        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 (int[] group : validMasks) {
                int groupMask = group[0], incompat = group[1];
                if ((groupMask & mask) == 0) {
                    int newMask = mask | groupMask;
                    dp[newMask] = Math.min(dp[newMask], dp[mask] + incompat);
                }
            }
        }
        return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
    }
}

var minimumIncompatibility = function(nums, k) {
    const n = nums.length, groupSize = n / k;
    const freq = {};
    for (const x of nums) freq[x] = (freq[x] || 0) + 1;
    for (const v of Object.values(freq)) if (v > k) return -1;

    const validMasks = [];
    for (let mask = 0; mask < (1 << n); ++mask) {
        if (mask.toString(2).split('1').length - 1 !== groupSize) continue;
        const seen = new Set(), vals = [];
        let valid = true;
        for (let i = 0; i < n; ++i) {
            if ((mask & (1 << i)) !== 0) {
                if (seen.has(nums[i])) { valid = false; break; }
                seen.add(nums[i]);
                vals.push(nums[i]);
            }
        }
        if (valid) {
            validMasks.push([mask, Math.max(...vals) - Math.min(...vals)]);
        }
    }

    const dp = Array(1 << n).fill(Infinity);
    dp[0] = 0;
    for (let mask = 0; mask < (1 << n); ++mask) {
        if (dp[mask] === Infinity) continue;
        for (const [groupMask, incompat] of validMasks) {
            if ((groupMask & mask) === 0) {
                const newMask = mask | groupMask;
                dp[newMask] = Math.min(dp[newMask], dp[mask] + incompat);
            }
        }
    }
    return dp[(1 << n) - 1] === Infinity ? -1 : dp[(1 << n) - 1];
};

Problem Description

Given an array nums of n integers, you are to divide these numbers into k groups of equal size such that:

Each group has exactly n / k elements.
No group contains duplicate elements.
Each element from nums must be used in exactly one group.

The incompatibility of a group is defined as the difference between its largest and smallest elements. The total incompatibility is the sum of incompatibilities for all groups.

Your task is to return the minimum possible total incompatibility across all valid groupings. If it is impossible to create such groups, return -1.

Constraints:

Each element can only be used once.
There may be only one valid solution, or none at all.

Example: For nums = [1,2,1,4] and k = 2, the answer is 4.

Thought Process

At first glance, the problem seems to ask for all possible ways to split the array into k groups with no duplicates in any group, and then choose the split with the smallest sum of incompatibilities. Brute-forcing all possible partitions is computationally expensive, especially since the number of ways to split an array grows rapidly with its size.

The key observations are:

We must avoid duplicate elements in any group; if any number appears more than k times, it's impossible.
Each group must have exactly n / k elements.
Our goal is to minimize the sum of the difference between max and min in each group.

A naive approach would try every possible grouping, but this is far too slow. Instead, we look for patterns or methods to prune invalid or suboptimal choices early, and to reuse solutions for subproblems (i.e., dynamic programming).

Solution Approach

We can model this problem as a bitmask dynamic programming problem, where each state represents a set of elements that have been used so far.

Step-by-step algorithm:

Check for impossibility:
- If any number appears more than k times, it's impossible to assign all instances to different groups without duplicates. Return -1 in this case.
Precompute all valid groups:
- Generate all subsets of size group_size = n / k that contain unique elements (no duplicates).
- For each valid subset, calculate its incompatibility (max - min).
- Store these as bitmasks for efficient lookup.
Dynamic Programming:
- Let dp[mask] represent the minimum total incompatibility for the set of used elements represented by mask.
- Initialize dp[0] = 0 (no elements used, incompatibility is 0).
- For each mask, try to add a valid group (represented as a bitmask) that does not overlap with mask.
- Update dp[new_mask] = min(dp[new_mask], dp[mask] + incompatibility_of_group).
- Continue until all elements are used (mask == (1 << n) - 1).
Return the answer:
- If dp[all_used] is still infinity, return -1 (no valid grouping found). Otherwise, return dp[all_used].

Why bitmask? Using bitmasks allows us to efficiently represent which elements have been used, and to quickly check for overlaps and combinations.

Why precompute valid groups? Since each group must be of fixed size and have no duplicates, we can precompute all possible valid groupings and their incompatibilities, saving time during the DP phase.

Example Walkthrough

Example: nums = [1,2,1,4], k = 2

Step 1: Each group must have 2 elements (group_size = 4 / 2 = 2).
Step 2: Precompute all valid pairs of elements with no duplicates:

[1,2] (incompatibility 1)
[1,4] (incompatibility 3)
[2,4] (incompatibility 2)

But since there are two 1's, we must use each in a different group.
Possible groupings:
- Group 1: [1,2], Group 2: [1,4] → incompatibility = 1 + 3 = 4
- Group 1: [1,4], Group 2: [1,2] → same as above
Any grouping with both 1's in the same group is invalid (would have duplicate).
Answer: Minimum incompatibility is 4.

The DP will efficiently explore these combinations, skipping invalid groupings, and find the minimum sum.

Time and Space Complexity

Brute-force approach:

Would try all possible partitions of the array into k groups, each of size n / k.
The number of such partitions is exponential (related to the Stirling numbers of the second kind), far too slow for practical input sizes.

Optimized DP approach:

There are 2^n possible masks (subsets of elements).
For each mask, we may check all valid groups (which is up to C(n, group_size)).
So, total time is O(2^n * C(n, group_size)), but the precomputation and pruning of invalid groups helps keep this manageable for small n (up to 16).
Space complexity is also O(2^n) for the DP array.

Why is this acceptable? For n ≤ 16, 2^n is about 65,536, which is feasible for modern computers.

Summary

The Minimum Incompatibility problem challenges us to partition the array into groups with unique elements, minimizing the sum of incompatibilities. Brute-force is not tractable, but by:

Checking for impossibility early,
Precomputing all valid groups,
Using bitmask dynamic programming to track used elements and build up solutions,

we can efficiently solve the problem for reasonable input sizes. The solution elegantly combines combinatorial enumeration with dynamic programming, demonstrating the power of bitmasking for subset problems.

AlgoMap.io

Want Help Cracking FAANG?