How hard is LeetCode 1681. Minimum Incompatibility?

LeetCode 1681. Minimum Incompatibility is rated Hard on LeetCode.

What is the time complexity of LeetCode 1681. Minimum Incompatibility?

The Python solution on this page runs in O(3^n).

What is the space complexity of LeetCode 1681. Minimum Incompatibility?

The Python solution on this page uses O(2^n) auxiliary space.

What topics does LeetCode 1681. Minimum Incompatibility cover?

LeetCode 1681. Minimum Incompatibility is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.

Minimum Incompatibility — LeetCode 1681 Python Solution

HardBit ManipulationArrayDynamic ProgrammingBitmask

Problem: #1681
Pattern: Bit Manipulation
Reading time: 7 min
Source: leetcode.com

The 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.

Example

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].

Python solution

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

Complexity

Measure	Complexity
Time	O(3^n)
Space	O(2^n) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1681. Minimum Incompatibility is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1681. Minimum Incompatibility?: LeetCode 1681. Minimum Incompatibility is rated Hard on LeetCode.
What is the time complexity of LeetCode 1681. Minimum Incompatibility?: The Python solution on this page runs in O(3^n).
What is the space complexity of LeetCode 1681. Minimum Incompatibility?: The Python solution on this page uses O(2^n) auxiliary space.
What topics does LeetCode 1681. Minimum Incompatibility cover?: LeetCode 1681. Minimum Incompatibility is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.