Minimum Incompatibility
01 · Problem
You are given an integer array nums and an integer k, where nums.length is divisible by k. Split all of the elements of nums into exactly k groups so that:
- every group has the same size,
nums.length / k, and - no group contains the same value twice.
The incompatibility of a group is its largest element minus its smallest element (a group of size 1 has incompatibility 0). Return the minimum possible sum of incompatibilities across all k groups, or -1 if no valid split exists.
02 · Examples
nums = [1,2,1,4], k = 2
4
The best split is [1,2] and [1,4], with incompatibilities 1 and 3, totalling 4. The two 1s must go to different groups.
nums = [6,3,8,1,3,1,2,2], k = 4
6
One optimal split is [1,2], [2,3], [6,8] and [1,3], giving 1 + 1 + 2 + 2 = 6.
nums = [5,3,3,6,3,3], k = 3
-1
There are four 3s but only three groups, so two 3s would have to share a group, which is not allowed.
03 · Constraints
- 011 <= k <= nums.length <= 16
- 02nums.length is divisible by k
- 031 <= nums[i] <= nums.length
04 · Optimal complexity
- Time
- O(3^n)
- Space
- O(2^n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.