Dividing an integer array into K groups such that every group have the smallest range

Question

So, more formally speaking, I'm getting N numbers and need to divide them into K groups that non of this groups are empty. The sum of ranges in each group need to be minimal. For example:

N = 4, K = 2 and the input is {5,3,1,1}.

One possible solution is {5,3},{1,1}. The sum of the ranges is 2 ((5-3)+(1-1)).

One more way to look at this is {1,1,3}{5} which is also 2 ((3-1)+(range of single number is 0)).

The range is always the difference between the biggest number in a group and the smallest number in the group.

When I searched the internet it was obvious that I need to use dynamic programming but all that I was come up with is solutions for K=2.

Can someone help?

Answer 1

1. Sort the array.
2. Let a_m be the m^th element of the array; then, let a_m = a_m – a_m–1 ∀m ∈ [1; N). The subtraction loop must run backwards to avoid altering a_m–1. a₀ ≡ 0.
3. Sort the resulting array, keeping initial indices of the elements sorted in the same order as the elements themselves.
4. Take the last K–1 indices: these, coupled with 0, are the indices for the first elements of the groups searched for.

Answer 2

With dynamic programmming, you came up with a solution for k = 2. Now think about how you can extend it to k = 3.

Say f2(n) returns the optimal solution for k=2 and first n numbers, f3(n) = f2(n-m) + err(n-m, n). That is one way of extending it.

Answer 3

You can do it in linear time, assuming your data is already sorted.

You can view your data on an axis between min_value and max_value. Trivially, clever solutions do not use non-contiguous groups, so any clever solution can be represented as a group of K segments on your axis, each segment [x1, x2] representing all the numbers in your data between x1 and x2.

The total cost of your solution is the sum of all the segment lengths, which is also max_value - min_value - (space between all your segments). The space between your segments is itself made of K - 1 "empty segments", i.e. with none of your input numbers in them, i.e. segments between two consecutive input numbers. What you want is to maximize the sum of the lengths of K - 1 such segments.

So all you have to do is (simple version):

• if necessary, sort your inputs
• compute B[i] = A[i+1] - A[i] for all i (A being the sorted input array)
• retrieve the K-1 biggest values of B (still linear time, can actually be done at the same time as previous step)
• These are the boundaries of your groups, so you can just iterate through A again to make the groups themselves (now that you have the boundaries) (this step can also be done together with the previous ones)

Necessarily all your groups will be non-empty if your number of different values is greater than K. If not, you can easily split groups containing duplicates of the same value to make all your groups non-empty.

Complexity (if already sorted): O(n*k) (at most) which is O(n) if K is constant. If not, just improve the search for the best K-1 segments to get O(n log(n)) at most

As is written, additional memory complexity can easily be O(K)

Answer 4

So in this problem we want to minimize the range of the groups.

So let say we have array A = {1,3,5,7,5,2}

The max range is in every array is max[a]-min[a], min range 0

We can use a variation of binary search to find minimum range, this answer is with the constraint that groups must contain consecetive numbers.

For the binary search we need to select boundaries which are given by the min and max range of the array.

This psuedo/java code would look something like this.

main(){
  int upper = max(A)-min(A); 
  int lower = 0;  


  while (true) {
    int mid =  upper-lower;  
    int blocks = calculateBlockCount(A, mid); 
    if (blocks < K) {
      upper = mid - 1;
    } 
    else if (blocks > K) {
      lower = mid + 1;
    } 
    else {
      return upper;
      break;
    }
  }
 }

    private static int calculateBlockCount(int[] array, int range) {
      int count = 0;
      int[] dumie_array;
      int dumie_array[].add[array[0]];

      for (int i = 0; i < array.length; i++) {
        int dumie_array[].add[array[i]]
         if (Func_range(dumie_array) > range) {
           count++;
           dumie_array = array[i];
         } 
         else {
           dumie_array.add(array[i]);
         }
      }
      return count;
    }

    private static int Func_range(int[] input) {
       int range = 0;
       range= max(input)-min(input)
       return sum;
     }

Hope stil helps

I think most of this works in java, only the add functionality which C++ has is not present. (did not want to write so much by making an arraylist.) But I think the idea of the program should be clear.
This is all based on this post Need explanation for algorithm searching minimal large sum. Which is a very similar problem.

Cheers, Gijs