1681. Minimum Incompatibility LeetCode Solution
In this guide, you will get 1681. Minimum Incompatibility LeetCode Solution with the best time and space complexity. The solution to Minimum Incompatibility problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Incompatibility solution in C++
- Minimum Incompatibility solution in Java
- Minimum Incompatibility solution in Python
- Additional Resources
Problem Statement of Minimum Incompatibility
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
Complexity Analysis
- Time Complexity: O(3^n)
- Space Complexity: O(2^n)
1681. Minimum Incompatibility LeetCode Solution in C++
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
constexpr int kMaxCompatibility = (16 - 1) * (16 / 2);
const int n = nums.size();
const int subsetSize = n / k;
const int maxMask = 1 << n;
const vector<int> incompatibilities =
getIncompatibilities(nums, subsetSize);
// dp[i] := the minimum possible sum of incompatibilities of the subset
// of numbers represented by the bitmask i
vector<int> dp(maxMask, kMaxCompatibility);
dp[0] = 0;
for (unsigned mask = 1; mask < maxMask; ++mask) {
// The number of 1s in `mask` isn't a multiple of `subsetSize`.
if (popcount(mask) % subsetSize != 0)
continue;
// https://cp-algorithms.com/algebra/all-submasks.html
for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
if (incompatibilities[submask] != -1) // valid subset
dp[mask] =
min(dp[mask], dp[mask - submask] + incompatibilities[submask]);
}
return dp.back() == kMaxCompatibility ? -1 : dp.back();
}
private:
static constexpr int kMaxNum = 16;
// Returns an incompatibilities array where
// * incompatibilities[i] := the incompatibility of the subset of numbers
// represented by the bitmask i
// * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
// `subsetSize`
vector<int> getIncompatibilities(const vector<int>& nums, int subsetSize) {
const int maxMask = 1 << nums.size();
vector<int> incompatibilities(maxMask, -1);
for (unsigned mask = 0; mask < maxMask; ++mask)
if (popcount(mask) == subsetSize && isUnique(nums, mask, subsetSize))
incompatibilities[mask] = getIncompatibility(nums, mask);
return incompatibilities;
}
// Returns true if the numbers selected by `mask` are unique.
//
// e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), `used` variable
// will be 0b1, which only has one 1 (less than `subsetSize`). In this case,
// we should return false.
bool isUnique(const vector<int>& nums, int mask, int subsetSize) {
unsigned used = 0;
for (int i = 0; i < nums.size(); ++i)
if (mask >> i & 1)
used |= 1 << nums[i];
return popcount(used) == subsetSize;
}
// Returns the incompatibility of the selected numbers represented by the
// `mask`.
int getIncompatibility(const vector<int>& nums, int mask) {
int mn = kMaxNum;
int mx = 0;
for (int i = 0; i < nums.size(); ++i)
if (mask >> i & 1) {
mx = max(mx, nums[i]);
mn = min(mn, nums[i]);
}
return mx - mn;
}
};
/* code provided by PROGIEZ */1681. Minimum Incompatibility LeetCode Solution in Java
class Solution {
public int minimumIncompatibility(int[] nums, int k) {
final int kMaxCompatibility = (16 - 1) * (16 / 2);
final int n = nums.length;
final int subsetSize = n / k;
final int maxMask = 1 << n;
final int[] incompatibilities = getIncompatibilities(nums, subsetSize);
// dp[i] := the minimum possible sum of incompatibilities of the subset
// of numbers represented by the bitmask i
int[] dp = new int[maxMask];
Arrays.fill(dp, kMaxCompatibility);
dp[0] = 0;
for (int mask = 1; mask < maxMask; ++mask) {
// The number of 1s in `mask` isn't a multiple of `subsetSize`.
if (Integer.bitCount(mask) % subsetSize != 0)
continue;
// https://cp-algorithms.com/algebra/all-submasks.html
for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
if (incompatibilities[submask] != -1) // valid submask
dp[mask] = Math.min(dp[mask], dp[mask - submask] + incompatibilities[submask]);
}
return dp[maxMask - 1] == kMaxCompatibility ? -1 : dp[maxMask - 1];
}
private static final int kMaxNum = 16;
// Returns an incompatibilities array where
// * incompatibilities[i] := the incompatibility of the subset of numbers
// represented by the bitmask i
// * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
// `subsetSize`
private int[] getIncompatibilities(int[] nums, int subsetSize) {
final int maxMask = 1 << nums.length;
int[] incompatibilities = new int[maxMask];
Arrays.fill(incompatibilities, -1);
for (int mask = 0; mask < maxMask; ++mask)
if (Integer.bitCount(mask) == subsetSize && isUnique(nums, mask, subsetSize))
incompatibilities[mask] = getIncompatibility(nums, mask);
return incompatibilities;
}
// Returns true if the numbers selected by `mask` are unique.
//
// e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), `used` variable
// will be 0b1, which only has one 1 (less than `subsetSize`). In this case,
// we should return false.
private boolean isUnique(int[] nums, int mask, int subsetSize) {
int used = 0;
for (int i = 0; i < nums.length; ++i)
if ((mask >> i & 1) == 1)
used |= 1 << nums[i];
return Integer.bitCount(used) == subsetSize;
}
// Returns the incompatibility of the selected numbers represented by the
// `mask`.
private int getIncompatibility(int[] nums, int mask) {
int mn = kMaxNum;
int mx = 0;
for (int i = 0; i < nums.length; ++i)
if ((mask >> i & 1) == 1) {
mx = Math.max(mx, nums[i]);
mn = Math.min(mn, nums[i]);
}
return mx - mn;
}
}
// code provided by PROGIEZ1681. Minimum Incompatibility LeetCode Solution in Python
class Solution:
def __init__(self):
self.kMaxNum = 16
def minimumIncompatibility(self, nums: list[int], k: int) -> int:
kMaxCompatibility = (16 - 1) * (16 // 2)
n = len(nums)
subsetSize = n // k
maxMask = 1 << n
incompatibilities = self._getIncompatibilities(nums, subsetSize)
# dp[i] := the minimum possible sum of incompatibilities of the subset
# of numbers represented by the bitmask i
dp = [kMaxCompatibility] * maxMask
dp[0] = 0
for mask in range(1, maxMask):
# The number of 1s in `mask` isn't a multiple of `subsetSize`.
if mask.bit_count() % subsetSize != 0:
continue
# https://cp-algorithms.com/algebra/all-submasks.html
submask = mask
while submask > 0:
if incompatibilities[submask] != -1: # valid submask
dp[mask] = min(dp[mask], dp[mask - submask] +
incompatibilities[submask])
submask = (submask - 1) & mask
return dp[-1] if dp[-1] != kMaxCompatibility else -1
def _getIncompatibilities(
self,
nums: list[int],
subsetSize: int,
) -> list[int]:
"""
Returns an incompatibilities array where
* incompatibilities[i] := the incompatibility of the subset of numbers
represented by the bitmask i
* incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
`subsetSize`
"""
maxMask = 1 << len(nums)
incompatibilities = [-1] * maxMask
for mask in range(maxMask):
if mask.bit_count() == subsetSize and self._isUnique(nums, mask, subsetSize):
incompatibilities[mask] = self._getIncompatibility(nums, mask)
return incompatibilities
def _isUnique(self, nums: list[int], mask: int, subsetSize: int) -> bool:
"""Returns True if the numbers selected by `mask` are unique."""
used = 0
for i, num in enumerate(nums):
if mask >> i & 1:
used |= 1 << num
return used.bit_count() == subsetSize
def _getIncompatibility(self, nums: list[int], mask: int) -> int:
"""
Returns the incompatibility of the selected numbers represented by the
`mask`.
"""
mn = self.kMaxNum
mx = 0
for i, num in enumerate(nums):
if mask >> i & 1:
mx = max(mx, num)
mn = min(mn, num)
return mx - mn
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.